C Recursion

In computer science, recursion is a programming technique that allows a function to call itself. This technique can be used to solve complex problems by breaking them down into smaller, more manageable subproblems. In C, recursion can be achieved by defining a function that calls itself within its own body.

What is Recursion?

Recursion is a technique that allows a function to call itself. The function can be thought of as breaking a problem down into smaller, more manageable subproblems. Each subproblem is then solved by calling the function again, with the subproblem as the new input. This process continues until the subproblem is small enough to be solved without further recursion.

One of the key features of recursion is that it can be used to solve problems that can be defined in terms of similar subproblems. For example, the factorial of a number can be defined as the product of all the positive integers less than or equal to that number. This definition can be easily translated into a recursive function, as we will see in the first example.

Examples of Recursion in C

Example 1: Factorial

The factorial of a number can be calculated using recursion. The following example demonstrates this by defining a recursive function to calculate the factorial of a given number:

1#include <stdio.h>
2
3int factorial(int n)
4{
5   if (n == 0)
6      return 1;
7   return n * factorial(n-1);
8}
9
10int main()
11{
12   int num = 5;
13   printf("Factorial of %d is %d\n", num, factorial(num));
14   return 0;
15}

The output of this program is:

1Factorial of 5 is 120

In this example, the function factorial takes an integer n as input and returns the factorial of that number. The function is defined recursively, with the base case being when n is equal to 0, in which case the function returns 1. In all other cases, the function returns n multiplied by the factorial of n-1. This continues until the base case is reached, at which point the function calls build up and the final answer is returned.

Example 2: Fibonacci Series

The Fibonacci series is another example of a problem that can be solved using recursion. The series is defined as the sum of the two preceding numbers in the series. The following example demonstrates how to calculate the nth number in the Fibonacci series using recursion:

1#include <stdio.h>
2
3int fibonacci(int n)
4{
5   if (n == 0)
6      return 0;
7   else if (n == 1)
8      return 1;
9   else
10      return fibonacci(n-1) + fibonacci(n-2);
11
12int main() { 
13	int num = 10; 
14	printf("The %dth number in the Fibonacci series is %d\n", num, 	fibonacci(num)); 
15	return 0; 
16}

Output:

1The 10th number in the Fibonacci series is 55

In this example, the function fibonacci takes an integer n as input and returns the nth number in the Fibonacci series. The function is defined recursively, with two base cases: when n is equal to 0, the function returns 0, and when n is equal to 1, the function returns 1. In all other cases, the function returns the sum of the fibonacci of n-1 and n-2. This continues until the base cases are reached, at which point the function calls build up and the final answer is returned.