You will encounter recursive problems in competitive programming. And when you attempt to solve these problems using different programming paradigms, you will first formulate recursive logic for them. In programming, recursive reasoning is extremely essential. It assists you in breaking down large complex problems into smaller ones. Hence, it is used all the time in almost every programming language.
What Is a Recursive Algorithm?
A recursive algorithm calls itself with smaller input values and returns the result for the current input by carrying out basic operations on the returned value for the smaller input. Generally, if a problem can be solved by applying solutions to smaller versions of the same problem, and the smaller versions shrink to readily solvable instances, then the problem can be solved using a recursive algorithm.
To build a recursive algorithm, you will break the given problem statement into two parts. The first one is the base case, and the second one is the recursive step.
- Base Case: It is nothing more than the simplest instance of a problem, consisting of a condition that terminates the recursive function. This base case evaluates the result when a given condition is met.
- Recursive Step: It computes the result by making recursive calls to the same function, but with the inputs decreased in size or complexity.
For example, consider this problem statement: Print sum of n natural numbers using recursion. This statement clarifies that we need to formulate a function that will calculate the summation of all natural numbers in the range 1 to n. Hence, mathematically you can represent the function as:
F(n) = 1 + 2 + 3 + 4 + …………..+ (n-2) + (n-1) + n
It can further be simplified as:
You can breakdown this function into two parts as follows:
Different Types of Recursion
There are four different types of recursive algorithms, you will look at them one by one.
-
Direct Recursion
A function is called direct recursive if it calls itself in its function body repeatedly. To better understand this definition, look at the structure of a direct recursive program.
|
int fun(int z){ fun(z-1); //Recursive call } |
In this program, you have a method named fun that calls itself again in its function body. Thus, you can say that it is direct recursive.
-
Indirect Recursion
The recursion in which the function calls itself via another function is called indirect recursion. Now, look at the indirect recursive program structure.
|
int fun1(int z){ int fun2(int y){ fun2(z-1); fun1(y-2) } } |
In this example, you can see that the function fun1 explicitly calls fun2, which is invoking fun1 again. Hence, you can say that this is an example of indirect recursion.
-
Tailed Recursion
A recursive function is said to be tail-recursive if the recursive call is the last execution done by the function. Let’s try to understand this definition with the help of an example.
|
int fun(int z) { printf(“%d”,z); fun(z-1); //Recursive call is last executed statement } |
If you observe this program, you can see that the last line ADI will execute for method fun is a recursive call. And because of that, there is no need to remember any previous state of the program.
-
Non-Tailed Recursion
A recursive function is said to be non-tail recursive if the recursion call is not the last thing done by the function. After returning back, there is something left to evaluate. Now, consider this example.
|
int fun(int z) { fun(z-1); printf(“%d”,z); //Recursive call is not the last executed statement } |
In this function, you can observe that there is another operation after the recursive call. Hence the ADI will have to memorize the previous state inside this method block. That is why this program can be considered non-tail recursive.
Moving forward, you will implement a C program that exhibits recursive algorithmic nature.
[Related reading: How to Learn Programming?]
Program to Demonstrate Recursion
You will look at a C program to understand recursion in the case of the sum of n natural numbers problem.
|
#include<stdio.h> int Sum(int n){ if(n==0){ return 0; } int temp = Sum(n-1); return n + temp; } int main() { int n; printf("Enter the natural number n to calculate the sum of n numbers: "); scanf("%d",&n); printf("%d",Sum(n)); } |
Output:
The output for the sum of n natural numbers program is represented in the image below.
Memory Allocation of Recursive Method
Each recursive call generates a new copy of the function on stack memory. Once the procedure returns some data, the copy is deleted from storage. Each recursive call maintains a separate stack because all parameters and other variables defined inside functions are kept on the stack. The stack is deleted after the value from the relevant function is returned.
Recursion is quite complicated in terms of resolving and monitoring the values at each recursive call. As a result, you have to maintain the stack and track the values of the variables specified in it. To better understand the memory allocation of recursive functions, examine the following example.
|
//Fibonacci program recursive Function int Fib(int num) { if ( num == 0 ) return 0; else if ( num == 1 ) return 1; else return ( Fib(num-1) + Fib(num - 2) ); } //Let’s say we want to calculate Fibonacci number for n=5 Fib(5) |
Now, have a look at this recursive Fibonacci code for n = 5. First, all stacks are preserved, each of which prints the matching value of n until n becomes zero. When the termination condition is achieved, the stacks are destroyed one at a time by returning 0 to their calling stack. To understand the call stack hierarchy, look at the figure below.
Conclusion
In this recursive algorithm tutorial, you learned what a recursive algorithm in programming is. After that, you discovered different types of recursion and their function call structures. You also looked at the programming implementation of the sum of n natural numbers recursive problem. Finally, you also understood the memory allocation of a recursive method inside the memory stack.
If you're looking for more in-depth training that goes beyond data structures and covers the foundations of interactive application development, Simplilearn's Post Graduate Program in Full Stack Web Development will prove ideal for you. The program is offered in collaboration with Caltech CTME and is a globally-recognized program designed to improve your odds of becoming a software developer by aiding you in mastering the art of software development. So, go ahead and start exploring!
Have any questions about this article on the recursive algorithm? If yes, please leave them in the comments section at the bottom of this page; we will respond to them soon!
