Recursion and its principle with example

Recursion is a process in which a function calls itself again and again. We use recursion to solve the bigger problem by dividing it into smaller similar sub-problems and then call them recursively.

In other words, we can also explain it as a problem is broken down into smaller subproblems. And a function applies the same algorithm to each subproblem until it reaches a base case. Here the base case is a straightforward and known solution.

Quescol 1-Minute Read

Recursion is a process in which a function calls itself repeatedly to solve smaller parts of a larger problem until it reaches a simple stopping point called the base case. It helps in solving complex problems by dividing them into smaller subproblems and combining their results to form the final answer. Recursion is widely used in mathematical problems and programming tasks where the same operation is applied repeatedly to smaller data.

Recursion Important Points:
• It works in two main parts — Base Case and Recursive Case.
• The Base Case stops the recursion to prevent infinite calls and provides a direct answer.
• The Recursive Case reduces the problem into smaller versions and calls the function again.
• Recursion follows the principle of “divide the problem into smaller subproblems” until the base case is reached.
• Common examples include Factorial (T(n) = T(n-1) + O(1)), Fibonacci Series (T(n) = T(n-1) + T(n-2) + O(1)), and Tree Traversals.
• It helps make problem-solving more structured, logical, and efficient for repetitive tasks.

Let’s Understand in Depth

What is Recursion?

Recursion is a process in which a function calls itself again and again to solve smaller parts of the same problem. Each time the function calls itself, it works on a smaller version of the original problem. This continues until it reaches a base case, which is the stopping condition that ends the repeated calls.

After reaching the base case, the function starts returning values step by step, combining them to form the final answer. Recursion is often used in problems like factorial, Fibonacci series, and tree traversal, where a task can be divided into similar smaller tasks.

Recursive function has two different parts

1. Base case
2. Recursive case

Base case

• The base case is used to terminate the task of recurring. If a base case is not defined, then the function will recur an infinite number of times.
• The base case gives the conditions in which the recursive calls will halt means collapse the recursion when you hit the base case.

Recursive case

• In the Recursive case, the problem space is made smaller and smaller dive deeper into the recursion in the recursive case.
• Recursive case simplifies a bigger problem into a number of simpler sub-problems and then calls them.

Example of Recursive function

1. Recursive Program to Calculate Factorial

Factorial Example

Factorial of a non-negative integer n, denoted as n!, is the product of all positive integers from 1 to n.

For example:

• 0! = 1 (by definition)
• 1! = 1 (only one number in the product)
• 5! = 5 x 4 x 3 x 2 x 1 = 120

C Program Example

#include<stdio.h>
long long fact(int num) {
  if (num == 0)
    return 1;
  else
    return (num * fact(num - 1));
}
int main() {
  int i, num, factorial = 1;
  printf("Enter a whole number to find Factorial = ");
  scanf("%d", & num);
  printf("Factorial of %d is: %llu", num, fact(num));
  return 0;
}

Output

Enter a whole number to find Factorial = 5
Factorial of 5 is: 120

Explanation

The above image explains how the factorial of 5 is found using recursion. It begins with fact(5), which means 5 multiplied by fact(4). Then fact(4) becomes 4 multiplied by fact(3), and this process keeps going until fact(0). The smallest case, fact(0), directly returns 1 — this is called the base case. After that, each result is return step by step: fact(1) = 1, fact(2) = 2, fact(3) = 6, fact(4) = 24, and finally, fact(5) = 120. This clearly shows how recursion works by breaking a big task into smaller ones and combining the results to find the final answer.

2. Fibonacci series Example

A Fibonacci series is a series where next term is equal to the sum of the previous two terms.

Tn=T(n−1)+T(n−2)  
 where  Tn, T(n−1)  and  T(n−2)  are  nth  term,  (n−1)th  term and  (n−2)th  terms respectively.
 And in Series first and second terms are 0 and 1 respectively.
 So,  T1=0  and  T2=1 

A Recursive method to Calculate the Fibonacci series

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

To Print the Fibonacci series

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

Complete Recursive Program to calculate Fibonacci series

#include<stdio.h>
#include<conio.h>
int fibonacci(int);
int main(){ 
	int n, i; 
	printf("Enter the number of element you want in series:"); 
	scanf("%d",&n); 
	printf("Fibonacci series is : \n");
	for(i=0;i<n;i++) { 
		printf("%d \n",fibonacci(i));
	}
	getch();
}
int fibonacci(int i){ 
	if(i==0) return 0; 
	else if(i==1) return 1; 
	else return (fibonacci(i-1)+fibonacci(i-2));
} 

Output

Enter the number of element you want in series:5
Fibonacci series is : 
0 
1 
1 
2 
3 

Advantages of Recursion:

• Simplifies Code: Makes complex problems easier to understand and write by dividing them into smaller subproblems.
• Reduces Code Length: Tasks like tree traversal, factorial, or Fibonacci can be written in fewer lines compared to loops.
• Natural Fit for Certain Problems: Problems that follow a repetitive pattern (like mathematical sequences or hierarchical structures) are best solved using recursion.
• Improves Problem Solving: Encourages a logical and structured approach to breaking down tasks.
• Cleaner Implementation: Helps represent mathematical equations or self-similar problems more clearly.

Disadvantages of Recursion (Detailed):

• High Memory Usage: Each recursive call takes space on the call stack, which increases memory usage.
• Slower Execution: Multiple function calls take more time compared to simple iterative solutions.
• Risk of Infinite Recursion: If the base case is missing or incorrect, it can lead to infinite calls and program crashes.
• Difficult Debugging: Tracing and understanding multiple recursive calls can be complex.
• Overhead in Function Calls: Each call adds overhead, which may not be efficient for large input sizes.