C

Examples Of Recursion In C – Most Detailed

With the help of examples, you will learn recursion in C programming in this guide. A recursive function is one that calls itself, and the process of calling itself is known as recursion.

Example 1 of Recursion: Fibonacci Sequence

In this example, we use recursion to display the Fibonacci sequence. The Fibonacci Sequence is a series of numbers in which each number is the sum of the two preceding numbers, for example: 0, 1, 1, 2, 3, 5, 8,…
The first and second terms must be specified, and the number from the third term onwards is equal to the sum of the previous two numbers. Here, we find the previous two terms by using the same function: fibonacci(n-1) and fibonacci(n-2) (n-2).

#include <stdio.h>

//recursive function, this function is calling itself
int fibonacci(int n) {
  if(n == 0){
    return 0;
  } else if(n == 1) {
  return 1;
  } else {
    return (fibonacci(n-1) + fibonacci(n-2));
  }
}

int main() {
  int n = 8;
  int i;
  printf("Fibonacci sequence of %d terms: " , n);

  for(i = 0;i<n;i++) {
    printf("%d ",fibonacci(i));
  }
}

Output:

Fibonacci sequence of 8 terms: 0 1 1 2 3 5 8 13

Example 2 of Recursion: Factorial

The factorial is as follows:

Factorial of n! = (n) * (n-1) * ... * 1

This formula is easy to remember: factorial of n = n * factorial of (n-1)

Factorial of n! = (n) * (n-1)!

Recursion can be used to implement this logic in a C program. The factorial(n) calls the factorial(n-1), the factorial(n-1) calls the factorial(n-2) and so on until the base case is reached, at which point n equals zero and returns 1.

#include <stdio.h>

//recursive function
int factorial(int n) {
  //base case
  if(n == 0) {
    return 1;
  } else {
    //calling itself
    return n * factorial(n-1);
  }
}

int main() {
  int num = 4;
  printf("Factorial of %d is: %d\n" , num , factorial(num));
}

Output:

Factorial of 4 is: 24

When is it appropriate to use recursion?

Recursion is useful for solving problems that can be divided into smaller, repetitive problems. In our factorial example, we saw that factorial of n is dependent on factorial of n-1, and so on. To solve that problem, we used recursion.
Similarly, in the fibonacci series example, we learned that a number in a series is the sum of the two preceding numbers, which means that any number of fibonacci series can be broken down from right to left by locating the two preceding numbers.

The Benefits and Drawbacks of Recursion

Advantages:

1. It is easier to write code. Instead of writing multiple functions to solve the same problem, a single function is used to solve the entire problem.
2. Frequently used in tree traversal because the root node of a tree has child nodes that have leaf nodes. Recursion, rather than any other programming technique, makes this easier to implement.

Disadvantages:

1. Makes analyzing the code difficult.
2. Consumes more memory as the repetitive calls continue to consume memory.
3. If not properly coded, it can run in an infinite loop.

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button