What Is C Recursion, How Does It Work And Code Examples?

C Recursion

Programming recursion is the process by which a function calls itself. This call can be either indirect, in which the function calls another function that calls the original function, or direct, in which the function calls itself explicitly within its own body. The expressions “circular definition” and “defining something in terms of itself” are occasionally used to characterise it. C allows for the recursive use of all functions.

When a problem’s answer can be described by repeatedly applying the same solution to subsets of the problem, recursion can be helpful. It can be an effective method for using fewer lines of code to tackle complicated logic problems. Some algorithms can be coded in the most straightforward and understandable way possible because they are inherently implemented recursively.

How Recursion Works

The system generates a new instance of a recursive function in memory whenever it is called. The function-call stack controls this procedure. The function’s initial call is delayed while it awaits the outcome of its recursive call. A lengthy chain of stack frames may result from this. The variables and parameters are locally stored on the stack for each function call.

A recursive process needs to follow two key guidelines in order to function properly and end:

Base Case(s): One or more base cases, or simple cases, are required for a recursive function. A recursive call is not necessary when the function is invoked with a base case because it knows how to solve it directly and just returns a result. This is the recursion’s termination point.

Recursive Step: The function splits the problem and calls itself with a significantly simplified version of the original problem for problems that are more complicated than the base case. With every call, this phase must guarantee that the issue gets easier. For the recursion to end, the series of these smaller issues must ultimately converge on the base situation.

The function returns a result to the instance of the function that called it when it reaches the base case. Until the initial call finishes and provides the final result, this process of returning results keeps going all the way back up the stack’s caller chain.

A recursive function must have a condition (such as an if statement) to cease calling itself when the base case is reached. This is an essential component. In the absence of this, the function would keep calling itself, filling the stack with parameters, return addresses, and function calls, resulting in a stack overflow error during runtime.

Recursion vs. Iteration (Loops)

Recursion is sometimes likened to loop-based iterative procedures (such as while, for, and do-while). Although the iterative version may occasionally be significantly more challenging and unclear, any program that can be written recursively can also be implemented iteratively. While iterative solutions typically utilize a set amount of memory, recursion can require more because it creates many function instances on the stack. In contrast to recursive algorithms, iterative algorithms may need the use of auxiliary pointers. Recursion can occasionally be quicker than an iterative method, even with the memory overhead.

Let’s examine some typical recursive function examples.

Factorial Calculation: The product of all positive integers less than or equal to n is the factorial of a non-negative integer n (written n!). The definition is n! = n * (n-1) and 0! = 1! when n > 0. A recursive implementation is a natural fit for this concept.

Example: The following is a recursive factorial function:

#include <stdio.h> // Required for printf()
// Recursive function to calculate the factorial of a non-negative integer
unsigned long long int factorial(int number) {
   // Base case: If number is 0 or 1, return 1.
   // This stops the recursion. 
   if (number <= 1) {
      return 1;
   }
   else {
      // Recursive step: Return number multiplied by factorial of (number - 1).
      // This calls the function itself with a smaller problem. 
      return (number * factorial(number - 1));
   }
}
int main(void) {
   // Calculate and display factorial(i) for a few numbers
   for (int i = 0; i <= 10; ++i) {
      printf("%d! = %llu\n", i, factorial(i));
   }
   return 0;
}

Output:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800

Explanation:

• When the number is 0 or 1, that is the base case. The recursive calls are stopped when the function simply returns 1.
• When the number is more than 1, the recursive step is performed. The result of multiplying a number by the result of performing the factorial with a value of -1 is returned by the function. The problem becomes simpler and finally reaches the base case because each recursive call is for a smaller integer.
• Up until factorial(1) is called, calling factorial(5) triggers calling factorial(4), which in turn triggers calling factorial(3). Before factorial(5) receives the result from factorial(4) and computes the final answer, factorial(1) hits the base case and returns 1. Factorial(2) receives 1 and computes 2 * 1 and returns 2. Factorial(3) receives 2 and computes 3 * 2 and returns 6.

Fibonacci Series: Every term after 0 and 1 in the Fibonacci series is the sum of the two terms before it. Fib(0) = 0, fib(1) = 1, and for n > 1, fib(n) = fib(n-1) + fib(n-2) is the recursive definition.

Example: The following is a recursive Fibonacci function:

#include <stdio.h> // Required for printf()
// Recursive definition of function fibonacci
unsigned long long int fibonacci(int n) {
   // Base cases: fib(0) is 0, fib(1) is 1.
   // These stop the recursion. 
   if (0 == n || 1 == n) {
      return n;
   }
   else {
      // Recursive step: fib(n) is the sum of the two preceding terms.
      // Calls itself twice with smaller problems. 
      return fibonacci(n - 1) + fibonacci(n - 2);
   }
}
int main(void) {
   // Calculate and display fibonacci(number) for 0-10 
   for (int number = 0; number <= 10; number++) {
      printf("Fibonacci(%d) = %llu\n", number, fibonacci(number));
   }
   printf("Fibonacci(20) = %llu\n", fibonacci(20)); // 
   // printf("Fibonacci(30) = %llu\n", fibonacci(30)); // 
   // printf("Fibonacci(40) = %llu\n", fibonacci(40)); // 
   return 0;
}

Output:

Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(4) = 3
Fibonacci(5) = 5
Fibonacci(6) = 8
Fibonacci(7) = 13
Fibonacci(8) = 21
Fibonacci(9) = 34
Fibonacci(10) = 55
Fibonacci(20) = 6765

Explanation:

• When n is 0 or 1, those are the base situations. The recursion for that path is terminated when the function returns n (0 or 1).
• When n exceeds 1, the recursive step occurs. When fibonacci is called with n – 1 and n – 2, the function gives the sum of the results. This illustrates a recursive step in which a single function invocation contains several recursive calls.

Although it can be difficult to understand, recursion is a powerful idea. Understanding how a function operates can be greatly aided by visualising its calls and returns using diagrams or debugging methods like showing intermediate values with indentation.

You can also read What Are The C String Handling Functions With Code Example?