Tail recursion

#recursion #type #tail recursion

1. Tail Recursion Sourav bhunia Id:1811100001057 Sister nivedita university

2. What is Recursion?? The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called as recursive function.

3. Recursion Type: 1.Tail Recursion 2.Head Recursion 3.Tree Recursion 4.Indirect Recursion 5.Nested Recursion

4. recursion TYPE Tree Recursion Indirect Recursion Nested Recursion

5. Tail Recursion: If a recursive function is calling itself and that recursive call is the last statement of the recursive function, then it is called as tail recursion. After the calling of the last statement there is nothing to execute in the recursive function.

6. Example of Tail Recursion : Void fun( int n) { if(n>0) { Printf (“% d”,n ); fun(n-1); } } >>>fun(3) Result  produced: 3,2,1 Last Statement of the recursive function

7. Tail Recursion or not .. Void fun( int n) { if(n>0) { //Some code fun(n-1)+n; } } All these operation perform in calling time only. The function not be performing any operation in returning time unless result of the function is known addition operation is not performed. In this case function has to perform operation on returning time , so this is not a tail recursion. It is also the last statement of the recursive function

8. Tail Recursion VS. Loop: Void fun( int n) { while(n>0) { Printf (“% d”,n ); n--; } } Result: 3 2 1 Passing value:fun (3) Every recursive function can be written as loop and vise versa.

9. Comparison : Time complexity: O(n) O(n) Space complexity: O(1) O(n) LOOP Tail recursion

10. Tail Recursive VS. Non-Tail Recursive 1.The tail recursive functions considered better than non tail recursive functions as tail-recursion can be optimized by compiler. 2.The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use

11. Conclusion: It is better to convert tail recursion into loop for better efficiency in terms of space. This is not true for all recursion or loop. It is efficient only in tail recursion.

12. Thank You!