Linear Recursion in C

Back to: C Tutorials For Beginners and Professionals

Linear Recursion in C Language with Examples

In this article, I will discuss Linear Recursion in C Language with Examples. Please read our previous article discussing Tree Recursion in C Language with Examples. At the end of this article, you will understand the following pointers:

1. What is Linear Recursion in C Language?
2. Multiple Real-Time Examples to Understand Linear Recursion in C Language
3. Advantages of Linear Recursion in C Language
4. Disadvantages of Linear Recursion in C Language
5. When Would We Use Linear Recursion in C Language?

What is Linear Recursion in C Language?

Linear recursion in the C language, or programming in general, is a form of recursion where a function calls itself only once in each step or execution path. This type of recursion is called “linear” because it creates a linear chain of function calls, where each function call leads to at most one other function call.

Linear recursion is simpler and more straightforward than other recursion forms, such as tree recursion or nested recursion. It is often used in scenarios where a problem can be broken down into a simpler version of the same problem, plus some additional operations. Here’s an example to illustrate linear recursion in C:

int sum(int n) {
    if (n <= 0) 
        return 0;
    else 
        return n + sum(n - 1); // Single recursive call
}

int main()
{
  // Calling the function
  int result = sum(5); // Calculates the sum of numbers from 1 to 5
  return 0;
}

In this example, the function sum is linear recursive. It calls itself once for each value of n until it reaches the base case (n <= 0). The recursion here is linear because there’s only one path of execution in each step, forming a straight line of recursive calls. For sum(5), the function calls itself with decreasing values of n (5, 4, 3, 2, 1, 0) until it reaches the base case, after which the calls return back up the chain.

Linear Recursion Real-Time Examples in C Language

Linear recursion is a form of recursion where a function makes, at most, one recursive call each time it is invoked. This is a straightforward form of recursion, often resembling a loop in procedural programming. Here are some real-time examples of linear recursion in the C language:

Example: Sum of Natural Numbers

#include <stdio.h>

// Linear recursive function to calculate the sum of first 'n' natural numbers
int sumOfNaturalNumbers(int n) {
    if (n <= 0)
        return 0; // Base case
    return n + sumOfNaturalNumbers(n - 1); // Recursive call
}

int main() {
    int number = 5;
    printf("Sum of first %d natural numbers is %d\n", number, sumOfNaturalNumbers(number));
    return 0;
}

Output: Sum of first 5 natural numbers is 15

Explanation:

• The function sumOfNaturalNumbers calculates the sum of the first n natural numbers.
• The base case is when n is 0 or less, in which case the function returns 0.
• Otherwise, the function returns n plus the result of a recursive call to itself with n – 1.
• This creates a linear chain of recursive calls, each reducing the problem size by 1.

Example: Factorial Calculation

#include <stdio.h>

// Linear recursive function to calculate factorial of a number
int factorial(int n) {
    if (n == 0)
        return 1; // Base case
    return n * factorial(n - 1); // Recursive call
}

int main() {
    int number = 5;
    printf("Factorial of %d is %d\n", number, factorial(number));
    return 0;
}

Output: Factorial of 5 is 120

Explanation:

• The function factorial calculates the factorial of a number n.
• The base case is when n is 0, where it returns 1.
• For other values of n, the function returns n multiplied by the result of a recursive call to itself with n – 1.
• This results in a linear sequence of recursive calls until the base case is reached.

Example: Printing Numbers in Descending Order

#include <stdio.h>

// Linear recursive function to print numbers from 'n' to 1
void printNumbersDescending(int n) {
    if (n <= 0)
        return; // Base case
    printf("%d ", n);
    printNumbersDescending(n - 1); // Recursive call
}

int main() {
    int number = 5;
    printNumbersDescending(number);
    return 0;
}

Output: 5 4 3 2 1

Explanation:

• The printNumbersDescending function prints numbers from n down to 1.
• If n is 0 or less, it returns, acting as the base case.
• Otherwise, it prints n and then makes a recursive call to itself with n – 1.
• This creates a linear chain of recursive calls, decrementing the number each time.

Example: Sum of an Array

This example demonstrates calculating the sum of elements in an array using linear recursion.

#include <stdio.h>

int sumArray(int arr[], int n) {
    if (n <= 0)
        return 0;
    return arr[n - 1] + sumArray(arr, n - 1); // Single recursive call
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Sum of array elements is %d\n", sumArray(arr, n));
    return 0;
}

Output: Sum of array elements is 15

Example: Reversing a String

Using linear recursion to reverse a string.

#include <stdio.h>
#include <string.h>

void reverseString(char *str, int start, int end) {
    if (start >= end)
        return;

    // Swap the characters
    char temp = str[start];
    str[start] = str[end];
    str[end] = temp;

    // Recursive call
    reverseString(str, start + 1, end - 1);
}

int main() {
    char str[] = "Hello World!";
    reverseString(str, 0, strlen(str) - 1);
    printf("Reversed string is: %s\n", str);
    return 0;
}

Output: Reversed string is: !dlroW olleH

Example: Linear Recursive Search

Implementing a linear search algorithm using recursion.

#include <stdio.h>

int linearSearch(int arr[], int n, int x) {
    if (n < 0)
        return -1;
    else if (arr[n] == x)
        return n;
    else
        return linearSearch(arr, n - 1, x); // Single recursive call
}

int main() {
    int arr[] = {2, 3, 4, 10, 40};
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = linearSearch(arr, n - 1, x);
    if (result == -1)
        printf("Element not found");
    else
        printf("Element found at index %d", result);
    return 0;
}

Output: Element found at index 3

Advantages and Disadvantages of Linear Recursion in C Language

Linear recursion in the C language, where a function calls itself once per execution path, has advantages and disadvantages, which are crucial for efficient programming.

Advantages of Linear Recursion in C Language

• Simplicity and Clarity: Linear recursion often leads to simpler, more readable code, especially for problems with a natural recursive structure. It’s easier to understand and implement compared to more complex forms of recursion.
• Natural Fit for Certain Problems: It’s well-suited for tasks that inherently follow a linear process, such as traversing a linked list, computing factorials, or performing binary searches.
• Reduction of Complex Problems: Linear recursion can break down complex problems into simpler, more manageable parts, where each step involves a single recursive call.
• Elegant and Direct Solutions: For certain problems, linear recursive solutions can be more elegant and direct than iterative counterparts, closely matching the theoretical or mathematical formulation of the problem.

Disadvantages of Linear Recursion in C Language

• Risk of Stack Overflow: Each recursive call consumes stack space. If the recursion depth is very large, it can lead to stack overflow issues.
• Performance Overhead: Linear recursion can be less efficient than iterative solutions due to the overhead of function calls and stack usage, especially for deep recursion.
• Potential for Infinite Recursion: If the base case is not properly defined or the recursive step does not converge towards it, it can result in infinite recursion, causing the program to crash or hang.
• Less Efficient for Simple Loops: For problems that can be easily solved with simple loops, linear recursion can be an overkill, introducing unnecessary complexity and performance overhead.
• Difficulty in Debugging: Debugging recursive functions can be more challenging compared to iterative ones, especially for those not accustomed to thinking recursively.
• Dependence on Compiler Optimization: In some cases, the efficiency of linear recursive functions depends on the compiler’s ability to optimize recursion, which is not always guaranteed.

When Would We Use Linear Recursion in C Language?

Linear recursion in C, or any programming language, is a recursion where each function call makes at most one recursive call. This is a simpler and more common form of recursion than tree or nested recursion. Here are some scenarios where linear recursion is particularly useful:

• Simple Divide and Conquer Problems: Linear recursion is ideal for problems where the task can be divided into two parts – one that is solved directly and another that is slightly smaller or simpler and can be solved by a recursive call. Examples include finding the maximum value in an array or binary search.
• Sequential Processing: When a problem involves processing a sequence of data in a linear fashion, such as traversing a linked list, linear recursion provides a straightforward approach.
• Simplifying Complex Iterations: In cases where an iterative solution is complex or difficult to understand, a linear recursive approach might offer a clearer and more elegant solution. This is often the case in algorithms that involve several conditional steps or complex loop invariants.
• Accumulating Results: Linear recursion can be used effectively in scenarios where you need to accumulate a result as you traverse through a data structure or a set of computations, such as calculating the sum of an array or the factorial of a number.
• Tail Recursion Optimization: If the linear recursion is tail-recursive (where the recursive call is the last action in the function), it can be optimized by some compilers into a loop, thus making it as efficient as iterative solutions in terms of space.

In the next article, I will discuss Mutual Recursion in C Language with Examples. In this article, I explain Linear Recursion in C Language with Examples. I hope you enjoy this article on linear recursion in C language with examples.