*is one of the interesting topic. The problems, which can be implemented using loops, can be implemented with*

**Recursion****Recursion**as well. But, most of us go with the looping solution. Today, I am going to set some light on how the same logic can be implemented using recursion. If we could derive a mathematical function for these type of problems, the implementation will be more easier. Lets understand it through some examples.

**Example 1 : Factorial**The factorial of a non-negative number is the multiplication of all the positive integers which are less than or equal to the number.

Suppose fact(n) is a function of n, where x is non-negative integer value. Hence

*fact(0) = fact(1) = 1*

*fact(2) = 2 * fact(1) = 2*

*fact(3) = 3 * fact(2) = 6*

*...*

*...*

*...*

*fact(n) = n * fact(n-1)*

So, the logic would be - If the value of n is 0 or 1 return 1, else return multiplication of n and value of function for (n-1).

int fact(int num) { if(num == 0 || num == 1) return 1; else return num * fact (num - 1); }

**Example 2 : Fibonacci****Series**

The Fibonacci series is a sequence of integers whose first and second terms are 0 and 1 respectively and each subsequent term is the sum of the previous two terms. Like - 0, 1, 1, 2, 3, 5, 8, 13, 21, .....

Suppose fibo(n) is a function of n which returns the term n of the fibonacci series and where n > 0 -

*fibo(1) = 0*

*fibo(2) = 1*

*fibo(3) = fibo(1) + fibo(2) = 1*

*fibo(4) = fibo(2) + fibo(3) = 2*

*fibo(5) = fibo(3) + fibo(4) = 3*

*...*

*...*

*...*

*fibo(n) = fibo(n-2) + fibo(n-1)*

So, the logic would be - If the value of n is 1 or 2 return (n-1), else return the addition of value of function for (n-2) and function for (n-1) .

int fibo(int num) { if(num == 1 || num == 2) return (num - 1); else return fibo(num - 2) + fibo(num - 1); }I hope, this post will really helpful.

But whenever a recursive call is made current set of storage is pushed into stack and another copy of storage vars is created for the next call . So be diligient while making such calls. As if when there is long chain of recursive call eventually would result in to stack out of memory.

ReplyDeleteThanks for the comment. Definitely need to take care on that front as well.

ReplyDeleteReally helpful.

ReplyDeletenice explanation

ReplyDeleteNice article. Tx.

ReplyDeleteJust to add, for recursion work efficiently, we should make our function re-entrant.

can you please provide some thing about threading and multi-threading.

ReplyDeleteThese two examples are good to understand recursion, but this implementation is very inefficient. The iterative implementation of factorial and fibonacci are much faster.

ReplyDeleteyes definitely, but I think that these could be the simplest implementation to understand the recursion

ReplyDeleteWow, that was quick!! Khatarnak response time hai ;)

ReplyDelete