Recursion in C: Understanding Recursive Functions

A function that calls itself is known as a recursive function. And, this technique is known as recursion.

Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.

Sample Code

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

The recursion continues until some condition is met to prevent it. To prevent infinite recursion, if...else statement (or similar approach) can be used where one branch makes the recursive call and other doesn't.

Program: Sum of Natural Numbers Using Recursion

#include <stdio.h>
int sum(int n);

int main()
{
    int number, result;

    printf("Enter a positive integer: ");
    scanf("%d", &number);

    result = sum(number);

    printf("sum=%d", result);
}

int sum(int num)
{
    if (num!=0)
        return num + sum(num-1); // sum() function calls itself
    else
        return num;
}

Output

When the above code is compiled and executed, it produces the following result ?

Enter a positive integer:
3
6

Initially, the sum() is called from the main() function with number passed as an argument.

Suppose, the value of num is 3 initially. During next function call, 2 is passed to the sum()function. This process continues until num is equal to 0.

When num is equal to 0, the if condition fails and the else part is executed returning the sum of integers to the main() function.

Fibonacci Series

The following example generates the Fibonacci series for a given number using a recursive function ?

#include <stdio.h>

int fibonacci(int i) {

   if(i == 0) {
      return 0;
   }
	
   if(i == 1) {
      return 1;
   }
   return fibonacci(i-1) + fibonacci(i-2);
}

int  main() {

   int i;
	
   for (i = 0; i < 10; i++) {
      printf("%d\t\n", fibonacci(i));
   }
	
   return 0;
}

Output:

When the above code is compiled and executed, it produces the following result ?

0	
1	
1	
2	
3	
5	
8	
13	
21	
34

Factorial

The following example generates the Fibonacci series for a given number using a recursive function ?

#include <stdio.h>

unsigned long long int factorial(unsigned int i) {

   if(i <= 1) {
      return 1;
   }
   return i * factorial(i - 1);
}

int  main() {
   int i = 5;
   printf("Factorial of %d is %d\n", i, factorial(i));
   return 0;
}

Output:

When the above code is compiled and executed, it produces the following result ?

Factorial of 5 is 120