DSA using C - Recursion

Overview

Recursion refers to a technique in a programming language where a function calls itself. The function which calls itself is called a recursive method.

Characteristics

A recursive function must posses the following two characteristics.

Base Case(s)

Set of rules which leads to base case after reducing the cases.

Recursive Factorial

Factorial is one of the classical example of recursion. Factorial is a non-negative number satisfying following conditions.

0! = 1

1! = 1

n! = n * n-1!

Factorial is represented by "!". Here Rule 1 and Rule 2 are base cases and Rule 3 are factorial rules.

As an example, 3! = 3 x 2 x 1 = 6

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

Recursive Fibonacci Series

Fibonacci Series is another classical example of recursion. Fibonacci series a series of integers satisfying following conditions.

F₀ = 0

F₁ = 1

F_n = F_n-1 + F_n-2

Fibonacci is represented by "F". Here Rule 1 and Rule 2 are base cases and Rule 3 are fibonnacci rules.

As an example, F₅ = 0 1 1 2 3

Example

#include <stdio.h>

int factorial(int n){
   //base case
   if(n == 0){
      return 1;
   } else {
      return n * factorial(n-1);
   }
}
int fibbonacci(int n){
   if(n ==0){
      return 0;
   }
   else if(n==1){
      return 1;
   } else {
      return (fibbonacci(n-1) + fibbonacci(n-2));
   }
}
main(){
   int n = 5;
   int i;
   printf("Factorial of %d: %d
" , n , factorial(n));
   printf("Fibbonacci of %d: " , n);
   for(i=0;i<n;i++){
      printf("%d ",fibbonacci(i));            
   }
}

Factorial of 5: 120
Fibbonacci of 5: 0 1 1 2 3