Recursion

Types of recursion

                    
#include <stdio.h>

void countdown(int n) {
    if (n == 0)
        return;
    printf("%d\n", n);
    countdown(n - 1);
}

int main() {
    countdown(5);
    return 0;
}
                    
                

                    
#include <stdio.h>

void function_B(int n);  // Forward declaration

void function_A(int n) {
    if (n == 0)
        return;
    printf("%d\n", n);
    function_B(n - 1);
}

void function_B(int n) {
    if (n == 0)
        return;
    printf("%d\n", n);
    function_A(n - 1);
}

int main() {
    function_A(5);
    return 0;
}
                    
                

Call Stack

• The call stack is a data structure used by the program to keep track of function calls. It stores the context of each function call, including parameters, local variables, and the return address. When a function is called, its context is push onto the top of the stack, and when a function completes or returns, its context is popped from the top of the stack.

Iteration vs. Recursion:

• Iteration and recursion are both techniques for solving problems, but they have some key differences:
• Iteration:
  • Iteration involves using loops (such as for or while) to repeatedly execute a block of code until a certain condition is met.
  • It typically uses mutable variables to keep track of the state and update it in each iteration.
  • It often requires explicit control flow statements, such as incrementing counters or updating indices.
  • It can be more efficient in terms of memory usage and execution speed for certain problems.
• Recursion:
  • Recursion involves breaking down a problem into smaller instances of the same problem and solving them recursively.
  • It relies on the call stack to handle the function calls and manage the state.
  • It often uses immutable variables and passes updated values as parameters to subsequent recursive calls.
  • It can provide a more concise and elegant solution for certain problems, but it may be less efficient in terms of memory usage and execution speed, especially for deeply nested recursive calls.
• Note: It's important to ensure that recursive functions have a base case (or multiple base cases) that terminates the recursion to avoid infinite loops.

Programs

                       
#include <stdio.h>
int sum(int n)
{
    if (n == 0)
        return 0;
    return sum(n - 1) + n;
}
int main()
{
    int r;
    r = sum(5);
    printf("%d", r);
    return 0;
}
                       
                   

                       
#include <stdio.h>
int fact(int n)
{
    if (n == 0)
        return 1;
    return fact(n - 1) * n;
}
int main()
{
    int r;
    r = fact(5);
    printf("%d", r);
    return 0;
}