Recursion can make your head spin!

Recursion is a programming concept where a function calls itself to solve a problem. To help you understand recursion in C, let's go through a simple example: calculating the factorial of a number.

The factorial of a non-negative integer (n), denoted as (n!), is the product of all positive integers less than or equal to (n). For example, (5! = 5 \times 4 \times 3 \times 2 \times 1 = 120).

Here's a recursive C function to calculate the factorial:

#include <stdio.h>

// Function to calculate factorial
int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n == 0 || n == 1) {
        return 1;
    } else {
        // Recursive case: n! = n * (n-1)!
        return n * factorial(n - 1);
    }
}

int main() {
    // Example usage
    int num = 5;
    printf("Factorial of %d is %d\n", num, factorial(num));

    return 0;
}

Let's break down how this recursive function works using the concept of a function stack:

1. Base Case:

   • The base case is the stopping condition for the recursion. In this example, if n is 0 or 1, the function returns 1 without making another recursive call. This prevents the function from calling itself indefinitely.

2. Recursive Case:

   • If n is greater than 1, the function calculates n * factorial(n - 1). This is the recursive step where the function calls itself with a smaller problem.

   • Each recursive call creates a new instance of the function with its own set of parameters and local variables.

3. Function Stack:

   • When the factorial function is called with an argument, a new frame is added to the function stack to store the local variables and the point of return.

   • The function stack keeps track of each function call and its local state.

   • As the base case is reached, the stack starts to unwind, and each function returns its result to the calling function.

Let's trace the function calls for factorial(5):

factorial(5)
  -> 5 * factorial(4)
      -> 4 * factorial(3)
          -> 3 * factorial(2)
              -> 2 * factorial(1)
                  -> 1
              <- 2 * 1 = 2
          <- 3 * 2 = 6
      <- 4 * 6 = 24
  <- 5 * 24 = 120

This shows how the function calls build up a stack, and as each function completes its computation, it returns a value, ultimately leading to the final result. Understanding the base case and the recursive case is crucial to implementing and understanding recursive functions.

Let's look at another classic example of recursion: calculating the nth number in the Fibonacci sequence. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. So, the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, and so on.

Here's a recursive C function to find the nth Fibonacci number:

#include <stdio.h>

// Function to calculate the nth Fibonacci number
int fibonacci(int n) {
    // Base case: Fibonacci of 0 or 1 is the number itself
    if (n == 0 || n == 1) {
        return n;
    } else {
        // Recursive case: Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

int main() {
    // Example usage
    int num = 6;
    printf("Fibonacci number at position %d is %d\n", num, fibonacci(num));

    return 0;
}

Now, let's break down how this recursive function works:

1. Base Case:

   • The base case is when n is 0 or 1. In this case, the function returns n because the Fibonacci of 0 is 0, and the Fibonacci of 1 is 1.

2. Recursive Case:

   • If n is greater than 1, the function calculates fibonacci(n - 1) + fibonacci(n - 2). This is the recursive step where the function calls itself with two smaller problems.

3. Function Stack:

   • The function stack keeps track of each function call and its local state. Each function call adds a new frame to the stack.

   • The recursive calls create a branching structure in the stack, with each call leading to further calls until the base case is reached.

Let's trace the function calls for fibonacci(6):

fibonacci(6)
  -> fibonacci(5) + fibonacci(4)
      -> fibonacci(4) + fibonacci(3)
          -> fibonacci(3) + fibonacci(2)
              -> fibonacci(2) + fibonacci(1)
                  -> fibonacci(1)    // Base case: returns 1
              <- fibonacci(0)         // Base case: returns 0
          <- fibonacci(1) + 1 = 2
      <- fibonacci(2) + 2 = 3
  <- fibonacci(3) + 3 = 6

This example illustrates how the recursive calls build a tree-like structure in the function stack, with each node representing a function call. The base cases ensure that the recursion eventually reaches a point where the function returns a value without making further recursive calls.

Let's explore another example, this time implementing a recursive function to calculate the sum of digits in a given integer. The result of adding up a number's individual digits is the sum of digits.

Here's the C code for the recursive function:

#include <stdio.h>

// Function to calculate the sum of digits
int sumOfDigits(int n) {
    // Base case: if the number has only one digit
    if (n < 10) {
        return n;
    } else {
        // Recursive case: sum = last digit + sum of digits in the remaining number
        return n % 10 + sumOfDigits(n / 10);
    }
}

int main() {
    // Example usage
    int num = 12345;
    printf("Sum of digits in %d is %d\n", num, sumOfDigits(num));

    return 0;
}

Now, let's break down how this recursive function works:

1. Base Case:

   • The base case is when the number n has only one digit (i.e., it's less than 10). In this case, the function simply returns the number itself.

2. Recursive Case:

   • If n has more than one digit, the function calculates n % 10 + sumOfDigits(n / 10). This is the recursive step where the function calls itself with the remaining digits of the number.

3. Function Stack:

   • The function stack keeps track of each function call and its local state. Each recursive call adds a new frame to the stack.

   • As the recursion progresses, the function works on smaller and smaller parts of the original number until it reaches the base case.

Let's trace the function calls for sumOfDigits(12345):

sumOfDigits(12345)
  -> 5 + sumOfDigits(1234)
      -> 4 + sumOfDigits(123)
          -> 3 + sumOfDigits(12)
              -> 2 + sumOfDigits(1)
                  -> 1    // Base case: returns 1
              <- 2 + 1 = 3
          <- 3 + 3 = 6
      <- 4 + 6 = 10
  <- 5 + 10 = 15

This example demonstrates how the recursive calls break down the problem into smaller subproblems until the base case is reached, and then the results are combined to obtain the final sum of digits. Understanding how the recursion progresses through smaller instances of the problem is key to grasping the concept.