Recursion in C | Recursive Function | Memory allocation of Recursive method

 

Recursion in C

Recursion is the process which comes into existence when a function calls a copy of itself to work on a smaller problem. Any function which calls itself is called recursive function, and such function calls are called recursive calls. Recursion involves several numbers of recursive calls. However, it is important to impose a termination condition of recursion. Recursion code is shorter than iterative code however it is difficult to understand.

Base Case: This is the termination condition that defines when the recursion should stop. When the base case is met, the function returns a result without making further recursive calls. It prevents the recursion from continuing indefinitely and defines the smallest, simplest instance of the problem.

Recursive Case: In this part of the function, it calls itself with modified arguments, effectively reducing the problem size towards the base case. The results of these recursive calls are combined to obtain the final result.

Here's a general structure of a recursive function in C:

c
return_type recursive_function(parameters) {
    // Base case: Check if the termination condition is met.
    if (base_case_condition) {
        return base_case_result;
    } else {
        // Recursive case: Call the function with modified arguments.
        modified_arguments = manipulate_parameters(parameters);
        return recursive_function(modified_arguments);
    }
}

Recursion can be a powerful technique for solving problems that exhibit a recursive structure. Some common examples where recursion is used include calculating factorials, computing Fibonacci numbers, traversing and searching in data structures like trees and graphs, and solving problems in a divide-and-conquer fashion.

Here's another example of recursion in C, this time with a function that calculates the sum of integers from 1 to a given positive integer n, and I'll include the Example of recursion in C

c
#include <stdio.h>

// Function to calculate the sum of integers from 1 to n recursively
int sum(int n) {
    // Base case: if n is 1, the sum is 1
    if (n == 1) {
        return 1;
    }
    // Recursive case: calculate the sum of integers from 1 to (n-1) and add n
    else {
        return n + sum(n - 1);
    }
}

int main() {
    int num;
    printf("Enter a positive integer: ");
    scanf("%d", &num);

    // Check for negative input
    if (num < 1) {
        printf("Input should be a positive integer.\n");
    } else {
        int result = sum(num);
        printf("The sum of integers from 1 to %d is %d\n", num, result);
    }

    return 0;
} 

Output:

Enter a positive integer: 5
The sum of integers from 1 to 5 is 15

In this example, the sum function recursively calculates the sum of integers from 1 to n. The base case is when n is 1, in which case the sum is 1. Otherwise, it recursively calls itself with n-1 and adds n to the result.

Recursive Function

A recursive function performs the tasks by dividing it into the subtasks. There is a termination condition defined in the function which is satisfied by some specific subtask. After this, the recursion stops and the final result is returned from the function.
Recursive functions are often used to solve problems that can be naturally expressed using recursion, such as problems involving tree structures (e.g., binary trees), searching and traversing data structures (e.g., depth-first search in graphs), and problems that can be solved using a divide-and-conquer approach.

Here's an example of a recursive function in C to calculate the factorial of a number:

c
#include <stdio.h>

// Recursive function to calculate the factorial of a number
int factorial(int n) {
    // Base case: When n is 0 or 1, the factorial is 1.
    if (n == 0 || n == 1) {
        return 1;
    } else {
        // Recursive case: Calculate factorial using recursion.
        return n * factorial(n - 1);
    }
}

int main() {
    int num;
    printf("Enter a non-negative integer: ");
    scanf("%d", &num);

    if (num < 0) {
        printf("Factorial is not defined for negative numbers.\n");
    } else {
        int result = factorial(num);
        printf("Factorial of %d is %d\n", num, result);
    }

    return 0;
}

 Output:

Enter a non-negative integer: 5
Factorial of 5 is 120

In this example, we have a function called factorial that calculates the factorial of a non-negative integer n. The function uses recursion with two parts:

1. Base Case: When n is 0 or 1, the factorial is 1, so the function returns 1.

1. 1. Recursive Case: For values of n greater than 1, the function calculates the factorial by calling itself with n-1 and multiplying the result by n.

   Memory allocation of Recursive method

   
   
   Each recursive call creates a new copy of that method in the memory. Once some data is returned by the method, the copy is removed from the memory. Since all the variables and other stuff declared inside function get stored in the stack, therefore a separate stack is maintained at each recursive call. Once the value is returned from the corresponding function, the stack gets destroyed.
   
   For recursive functions, this means that each recursive call creates a new stack frame, and when the recursion reaches the base case and starts returning values, those stack frames are gradually removed from the stack.
   
   Let's consider a simple example of a recursive function to calculate the factorial of a number:

   c
   #include <stdio.h>
   
   int factorial(int n) {
       if (n <= 1) {
           return 1;
       } else {
           return n * factorial(n - 1);
       }
   }
   
   int main() {
       int result = factorial(5);
       printf("Factorial of 5 is %d\n", result);
       return 0;
   }

   
   
   In this example, each recursive call to the factorial function creates a new stack frame with its own set of local variables, including n. As the recursion progresses, more and more stack frames are pushed onto the call stack.
   
   For factorial(5), the call stack might look something like this:

   
   factorial(5)
   factorial(4)
   factorial(3)
   factorial(2)
   factorial(1)

   When the base case n <= 1 is reached (in this case, when n becomes 1), the recursion starts to unwind. The stack frames are popped off the call stack one by one, and as they are removed, the local variables for each frame are deallocated automatically. The return values are propagated back up the call stack until the final result is obtained.