Recursion in C
Recursion in C is a programming technique where a function calls itself directly or indirectly to solve a problem. This approach is based on the principle of solving a large problem by breaking it down into smaller, more manageable sub-problems that are of the same type as the original. Each recursive call reduces the original problem into a simpler version until it reaches a base case, which is a condition where the problem can be solved directly without further recursion. This base case is crucial as it provides the stopping criterion for the recursion and prevents it from continuing indefinitely. Recursive functions are particularly useful for tasks that can naturally be divided into similar sub-tasks, such as searching, sorting, and traversing complex data structures like trees and graphs.
Recursion works in C because each time a recursive function calls itself, a new set of local variables and parameters are placed on the program's call stack. This stack keeps track of each recursive call's state, allowing the function to return to its previous state once the current call completes. As the recursive calls are unwound and the stack unwinds, the solution to each sub-problem is combined to solve the overall problem. This mechanism leverages the stack's LIFO (Last In, First Out) nature to manage the function's execution order and memory use efficiently. Although recursion can be elegant and succinct, it's essential to handle it carefully to avoid excessive memory use and potential stack overflow errors if the recursion depth becomes too great.
Here's a simple recursive program in C to compute the factorial of a number. Factorial of a number n (denoted as n!) is the product of all positive integers less than or equal to n. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.
#include <stdio.h>
// Function declaration
long factorial(int n);
int main() {
int number = 5;
printf("Factorial of %d = %ld", number, factorial(number));
return 0;
}
// Recursive function to find factorial of n
long factorial(int n) {
if (n == 0) // Base case
return 1;
else
return n * factorial(n - 1); // Recursive call
}
This program defines a recursive function factorial that takes an integer n and returns its factorial. The recursion base case is when n is 0, at which point the function returns 1, because 0! is defined to be 1. If n is not 0, the function calls itself with n - 1 and multiplies the result by n, gradually reducing the problem size with each recursive call until it reaches the base case.
Let's illustrate how recursion works for factorial(3) by representing the call stack and local variables at each stage.
Initial Call: factorial(3)
Call Stack | Local Variables
---------------------------------- | ----------------
factorial(3) | n = 3
↓ calls factorial(2) |
factorial(2) | n = 2
↓ calls factorial(1) |
factorial(1) | n = 1
↓ calls factorial(0) |
factorial(0) | n = 0 (Base case reached, returns 1)
← returns 1 |
← returns 1 * 1 = 1 |
← returns 2 * 1 = 2 |
← returns 3 * 2 = 6 |
---------------------------------- | ----------------
Detailed Explanation
factorial(3) is called from
main. The call stack now hasfactorial(3).Inside
factorial(3), sincenis not0, it callsfactorial(2). The stack grows to includefactorial(2), with each level having its own localn.This process repeats until
factorial(0)is called, which is the base case. At this point,n == 0, sofactorial(0)returns1without making more recursive calls.As the stack unwinds, each call to
factorialreturns to its caller, multiplying the return value bynat each level.When the initial call
factorial(3)resumes, it has received all the return values from the recursive calls, completing the computation:3 * 2 * 1 * 1 = 6.Finally,
factorial(3)returns6tomain, which prints the result.
Here's another simple recursive program in C to sum all the numbers in an array. This approach breaks down the task by adding the current element to the result of summing the rest of the array.
#include <stdio.h>
// Function declaration
int sumArray(int arr[], int n);
int main() {
int arr[] = {1, 2, 3, 4, 5}; // Example array
int n = sizeof(arr) / sizeof(arr[0]); // Number of elements in array
printf("Sum of array elements = %d", sumArray(arr, n));
return 0;
}
// Recursive function to sum all elements in an array
int sumArray(int arr[], int n) {
if (n <= 0) // Base case
return 0;
else
return arr[n - 1] + sumArray(arr, n - 1); // Add last element and recurse with the rest
}
This program includes a recursive function sumArray that takes an array arr and its size n as arguments, returning the sum of all elements in the array. The base case for the recursion is when n <= 0, in which case the function returns 0. For any other value of n, the function returns the sum of the last element in the array (arr[n - 1]) and the result of a recursive call to sumArray with the rest of the array (n - 1 elements).
Let's illustrate how the recursion works for sumArray(arr, 5) with arr = {1, 2, 3, 4, 5}, by representing the call stack and local variables at each stage.
Initial Call: sumArray(arr, 5)
Call Stack | Local Variables
---------------------------------- | --------------------------------
sumArray(arr, 5) | arr = {1,2,3,4,5}, n = 5
↓ calls sumArray(arr, 4) |
sumArray(arr, 4) | arr = {1,2,3,4,5}, n = 4
↓ calls sumArray(arr, 3) |
sumArray(arr, 3) | arr = {1,2,3,4,5}, n = 3
↓ calls sumArray(arr, 2) |
sumArray(arr, 2) | arr = {1,2,3,4,5}, n = 2
↓ calls sumArray(arr, 1)
sumArray(arr, 1) | arr = {1,2,3,4,5}, n = 1
↓ calls sumArray(arr, 0)
sumArray(arr, 0) | arr = {1,2,3,4,5}, n = 0 (Base case reached, returns 0)
← returns 0 |
← returns 1 + 0 = 1|
← returns 2 + 1 = 3 |
← returns 3 + 3 = 6 |
← returns 4 + 6 = 10 |
← returns 5 + 10 = 15 |
---------------------------------- | --------------------------------
Detailed Explanation
sumArray(arr, 5) is called from
main, starting the recursion with the whole array.The function calls itself with
n - 1, reducing the array's effective size by one each time (ignoring the last element).When
nbecomes0, the base case is reached, andsumArrayreturns0, which means there are no elements left to add.As the stack unwinds, each level of recursion adds its last element (
arr[n - 1]) to the sum returned from its recursive call, building up the total sum.When the initial call
sumArray(arr, 5)resumes, it has aggregated the sum of all elements in the array through its recursive calls:5 + 10 = 15.Finally,
sumArray(arr, 5)returns15tomain, which prints the result.
Here's another simple recursive program in C to compute the (n)th Fibonacci number. 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. That is, the sequence starts 0, 1, 1, 2, 3, 5, 8, 13, ..., and the (n)th Fibonacci number is the sum of the ((n-1))th and ((n-2))th numbers.
#include <stdio.h>
// Function declaration
int fibonacci(int n);
int main() {
int n = 5;
printf("Fibonacci(%d) = %d", n, fibonacci(n));
return 0;
}
// Recursive function to find the nth Fibonacci number
int fibonacci(int n) {
if (n <= 1) // Base case
return n;
else
return fibonacci(n - 1) + fibonacci(n - 2); // Recursive call
}
The program includes a recursive function fibonacci that calculates the (n)th Fibonacci number. If n is 0 or 1, the function returns n, which corresponds to the base cases of the Fibonacci sequence. For any other value of n, the function returns the sum of the two preceding Fibonacci numbers by calling itself with n - 1 and n - 2.
Let's illustrate how the recursion works for fibonacci(4), by representing the call stack and local variables at each stage.
Initial Call: fibonacci(4)
Call Stack | Local Variables
---------------------------------- | ----------------
fibonacci(4) | n = 4
↓ calls fibonacci(3) |
fibonacci(3) | n = 3
↓ calls fibonacci(2) |
fibonacci(2) | n = 2
↓ calls fibonacci(1) |
fibonacci(1) | n = 1 (Base case, returns 1)
↓ calls fibonacci(0) |
fibonacci(0) | n = 0 (Base case, returns 0)
← returns 1 + 0 = 1 |
↓ calls fibonacci(1) |
fibonacci(1) | n = 1 (Base case, returns 1)
← returns 1 + 1 = 2 |
↓ calls fibonacci(2) |
fibonacci(2) | n = 2
↓ calls fibonacci(1) |
fibonacci(1) | n = 1 (Base case, returns 1)
↓ calls fibonacci(0) |
fibonacci(0) | n = 0 (Base case, returns 0)
← returns 1 + 0 = 1 |
← returns 2 + 1 = 3 |
↓ calls fibonacci(2) |
fibonacci(2) | n = 2
↓ calls fibonacci(1) |
fibonacci(1) | n = 1 (Base case, returns 1)
↓ calls fibonacci(0) |
fibonacci(0) | n = 0 (Base case, returns 0)
← returns 1 + 0 = 1 |
← returns 3 + 1 = 4 |
---------------------------------- | ----------------
Detailed Explanation
fibonacci(4) is the initial call. It needs to compute the 4th Fibonacci number.
It breaks down the problem by calling fibonacci(3) and fibonacci(2), as the 4th Fibonacci number is the sum of the 3rd and 2nd.
Each of those calls further breaks down into smaller calls until they hit the base cases (fibonacci(1) or fibonacci(0)), which directly return
1or0, respectively.As the stack unwinds, the return values from the base cases are summed up following the Fibonacci sequence logic.
This process illustrates the concept of recursion very well but also highlights a significant inefficiency. Each fibonacci(n) call results in two more calls, leading to an exponential increase in the number of calls, many of which are repeated.
To demonstrate the recursive calculation of (x^n) (where (x) is the base and (n) is a non-negative integer exponent), let's write a simple C function. This function will use a divide-and-conquer approach to efficiently compute power values by splitting the problem into smaller sub-problems.
#include <stdio.h>
// Function declaration
double power(double x, int n);
int main() {
double x = 2.0;
int n = 4;
printf("%f raised to the power of %d is %f", x, n, power(x, n));
return 0;
}
// Recursive function to calculate x^n
double power(double x, int n) {
if (n == 0) // Base case
return 1;
else if (n % 2 == 0) // If n is even
return power(x, n / 2) * power(x, n / 2);
else // If n is odd
return x * power(x, n / 2) * power(x, n / 2);
}
The power function computes (x^n) recursively. If (n) is 0, it returns 1, following the mathematical convention that any number raised to the power of 0 equals 1. For positive (n), the function checks if (n) is even or odd. If (n) is even, it calculates (x^{n/2}) and then squares it, effectively calculating (x^n). If (n) is odd, it calculates (x^{n/2}), squares it, and then multiplies by (x) to account for the extra (x) factor in odd powers.
Let's illustrate how the recursion works for power(2, 4), by representing the call stack and local variables at each stage.
Initial Call: power(2, 4)
Call Stack | Local Variables
----------------------------------- | ----------------
power(2, 4) | x = 2, n = 4
↓ calls power(2, 2) twice |
power(2, 2) | x = 2, n = 2
↓ calls power(2, 1) twice |
power(2, 1) | x = 2, n = 1
↓ calls power(2, 0) twice |
power(2, 0) | x = 2, n = 0 (Base case, returns 1)
← returns 1 |
↓ (repeat for second call, returns 1)
← returns 2 * 1 * 1 = 2 |
← returns 2 * 2 = 4 |
← returns 4 (repeat for second call, returns 4)
← returns 4 * 4 = 16 |
----------------------------------- | ----------------
Detailed Explanation
power(2, 4) is the initial call. It aims to compute (2^4).
Since (n) is even, it calls power(2, 2) twice. The reason for two calls is due to the squaring step in the function (this can be optimized, as explained later).
power(2, 2) then checks that (n) is even again and calls power(2, 1) twice.
power(2, 1) finds (n) is odd, so it multiplies (x) by the result of power(2, 0) called twice (each returning 1).
Once the base case power(2, 0) returns 1, the calls start unwinding. power(2, 1) calculates (2 \times 1 \times 1 = 2), then power(2, 2) calculates (2 \times 2 = 4), and finally, the initial call power(2, 4) calculates (4 \times 4 = 16).
This example illustrates recursion's power and its stack-based execution. However, it also shows an inefficiency due to the repeated calculations of the same values. A more efficient approach would store the result of power(x, n/2) in a variable and use it to calculate the final result, thereby reducing the number of recursive calls. This optimization is a form of memoization, which is particularly useful in recursive algorithms to improve performance.