C Programming #38: Function - recursion

Following article will discuss the concept of recursion in function. If function is defined as simplified form of itself then it is called as recursion. In simplest terms if function calls itself then it is called recursion.

Lets take an example :-
We already know the definition of factorial(n) as

factorial(n) = n * (n - 1) * (n - 2) ..... 3 * 2 * 1

Following is recursive definition 

factorial(n) = n * factorial(n - 1)

All recursive definition needs a trivial solution (also called stop condition). In-case of factorial it is factorial(1) = 1, which is assumed. Hence full recursive definition is 

factorial(n) = n * factorial(n - 1) 
factorial(1) = 1    -> Trivial solution.

Lets implement it -

#include <stdio.h>
int factorial(int);
int main() 
{
   int fact, n = 4;

   fact = factorial(n);

   printf("Factorial of n is %d\n", fact);

   return 0;
}
int factorial(int x)
{
   int temp_fact;
   if(x == 1) {
      temp_fact = 1;
   } else {
      temp_fact = x * factorial(x - 1);
   }
   return temp_fact;
}

Output will be 

Factorial of n is 24

The Simplified stack for above program will look as follows

Below diagram shows in-dept of function call.

Lets dive into into it in detail of above diagram-

Analyzing we need to follow two paths

1. Parameter passed to recursive function (Forward Path)
2. Return value from the recursive path (Return Path)

Systematic analysis of any recursive function is a must to understand it properly. Example i took is not a problem that is inherently recursive. It can be easily converted into iterative solution using for loop.

It is already covered in following article.

Links

Next Article - C Programming #39: Array - single dimension
Previous Article - C Programming #37: Function - Stack

All Article - C Programming