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.

We already know the definition of factorial(n) as

Following is recursive definition

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

Lets implement it -

Output will be

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

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.

Previous Article - C Programming #37: Function - Stack

All Article - C Programming

*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

- Parameter passed to recursive function (Forward Path)
- 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 dimensionPrevious Article - C Programming #37: Function - Stack

All Article - C Programming

## No comments :

## Post a Comment