Recursion and Stack

Recursion is a process in which a function calls itself directly or indirectly based on some termination condition.

When a function is called, the control goes to the called function, and the state of the caller function is stored in the stack, which means the return address and the values of local and formal variables are pushed onto the stack. Once the return statement is encountered, control comes back to the previous call, by using the return value present in the stack and it substitutes the return value to the call.

---

Iteration vs. Recursion

---

Iteration	Recursion
It is a process of executing a group of statements until some specified condition is satisfied.	The function calls itself until a termination condition is true.
The process involves some clear-cut processing sections such as initialization, decision, computation, and updation.	There will be an exclusive stopping condition within the recursive body of the function.
These functions exert very fast and occupy less memory and it can be easy.	It occupies more memory because of more number of times pushing and popping items. Obviously, it is expensive.

Note that all the recursive problems are not solvable in the iterative approach.

---

Types of Recursion

---

The recursive approaches are classified as follows:

Direct Recursion

When a function calls itself directly.

Indirect Recursion

When a function calls another function, which in turn calls this function.

Based on the definition of the recursive functions, they are classified as follows.

Tail Recursion

A recursion is said to be a tail recursion if there are no pending operations to be performed on return from a recursive call.

In tail recursion, there is a single recursive call that occurs at the very end of the function implementation. In other words, when the recursive call is made there are no more statements to be executed in the function. The single recursive call is the last thing to happen when the function is executed.

Tree Recursion

Another variant of the recursion technique is where the pending operation does involve another recursive call to the function. For example, Fibonacci Series.

---

Examples On Recursion

---

So far we have understood the recursion procedure. Now in this context, we will give some examples of recursion which may be helpful for readers.

Factorial of a number in a normal recursive way

#include <stdio.h> long int factorial(int n) { if(n<=1) return 1; else return (n*factorial(n-1)); } int main() { int n; printf("\nenter the number:"); scanf("%d",&n); printf("\nfactorial=%d",factorial(n)); return 0; }

GCD of two numbers in normal recursive way

#include <stdio.h> int gcd(int m,int n) { if(n==0) return m; if(m < n) return (gcd(n,m)); return (gcd(n,m%n)); } int main() { int m,n,result,temp; printf("\nenter two numbers:"); scanf("%d %d",&m,&n); if(m < n) { temp=m; m=n; n=temp; } result=gcd(m,n); printf("\nGCD is:%d",result); return 0; }

Fibonacci series in normal recursive way

#include <stdio.h> int Fibonacci(int); int main() { int n, i = 0, c; printf("\nenter the number of terms:"); scanf("%d",&n); printf("Fibonacci series\n"); for ( c = 1 ; c <= n ; c++ ) { printf("%d ", Fibonacci(i)); i++; } return 0; } int Fibonacci(int n) { if ( n == 0 ) return 0; else if ( n == 1 ) return 1; else return ( Fibonacci(n-1) + Fibonacci(n-2) ); }

Factorial of a number using Tail recursion

#include <stdio.h> int fac(int n,int fact) { if(n==1) return fact; else return (fac(n-1,n*fact)); } int main() { int n,val; printf("\nenter the number:"); scanf("%d",&n); if(n < 0) printf("\nfactorial is not possible"); else { if(n==0) printf("\nfactorial is 1"); else { val=fac(n,1); printf("\nfactorial is %d",val); } } return 0; }

Fibonacci series using Tail recursion

#include <stdio.h> int fibo_tail(int x,int next,int result) { if(x==1) printf("%d",result); else { printf("%d ",result); fibo_tail(x-1,next+result,next); } return 0; } int main() { int x; printf("\nenter the number of terms:"); scanf("%d",&x); fibo_tail(x,1,0); return 0; }

Hope, the above two examples will be helpful for readers to understand tail recursion.

Happy Exploring!