Recursive Algorithm Details

 Recursive Algorithm Description

What is 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. 

How to build resursive 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.
•  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:

  

Types of Recursions

There are four different types of recursive algorithms.

1-Direct Recursion

A function is called direct recursive if it calls itself in its function body repeatedly.

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.

2-Indirect Recursion

The recursion in which the function calls itself via another function is called indirect recursion.

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.

3-Tailed Recursion

A recursive function is said to be tail-recursive if the recursive call is the last execution done by the function. 

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.

4-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

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.