# Recursive Function in C

In C, a function can call itself. This process is known as recursion.

A function that calls itself is called a recursive function. At first, recursive may appear a little tricky. Let’s take a simple example:

In the beginning `main()` function called `rec()`, then inside `rec()` function, it called itself again. As you can guess this process will keep repeating indefinitely. So, in a recursive function, there must be a terminating condition to stop the recursion. This condition is known as the base condition.

Often recursion can be used where loops can be used. Generally, recursive solutions are elegant but less efficient than loop solutions. So why use recursion at all? because some algorithms can be implemented more clearly and easily using recursion like quicksort.

The recursive function works in two phases:

1. Winding phase.
2. Unwinding phase.

Winding phase: In Winding phase, the recursive function keeps calling itself. This phase ends when the base condition is reached.

Unwinding phase: When the base condition is reached Unwinding phase starts and control returns back to the original call.

Let’s take an example:

Example 1:

Expected Output:

How it works:

Winding phase 1:

First, `main()` calls the `rec()` function with an actual argument of 1. As a result, the formal argument of `rec()` function is initialized with the value of `1`. In line 14, `printf()` statement is executed and prints the value of `n`.

Then the if condition `(n < 3)` i.e `(1 < 3)` is tested, since it is true, `rec()` level 1 called `rec()` level 2 with an actual argument of 2.

Winding phase 2:

Now control again passes to level 2 `rec()` function with a formal argument of `2`. The `printf()` statement in line 14 is again executed and prints.

If condition `(n < 3)` i.e `(2 < 3)` is tested again, since it is true, level 2 `rect()` called level 3 `rec()` with an actual argument of `3`.

Winding phase 3:

Once the control passes to level 3 `rec()` function with a formal argument of `3`. The `printf()` statement in line 14 is again executed and prints.

If condition `(n < 3)` i.e `(3 < 3)` is checked but this time it is false, as a result, call to `rec()` is skipped. Now our program has reached the base condition. This completes the winding phase.

Unwinding phase 1:

In this level 3 call, for the first time `printf()` statement in line 21 is executed and prints.

As soon as `rec()` function in winding phase 3 ends, the control passes back to its caller (i.e the level 2 call) and execution resumes from there.

Unwinding phase 2:

Since the last statement executed in the level 2 call was the call to level 3 `rec()` function inside the if statement, Hence, level 2 `rec()` function resumes with the following statement, which prints.

Then the level 2 `rec()` function ends, passing the control to level 1 `rec()` function.

Unwinding phase 3:

Just like in level 2 `rec()` call, execution in level 1 rec() resumes with the statement following if statement, which prints.

Then the level 1 rec() ends, and control passes back to `main()` function.

Example 2:

The following program calculates the factorial of a number using recursion.

Expected Output:

How it works:

Let’s say we want to calculate factorial of `5`.

`main()` calls `factorial(5)`
since `5 != 0``factorial(5)` calls `factorial(4)`
since `4 != 0``factorial(4)` calls `factorial(3)`
since `3 != 0``factorial(3)` calls `factorial(2)`
since `2 != 0``factorial(2)` calls `factorial(1)`
since `1 != 0``factorial(1)` calls `factorial(0)`

When `factorial()` is called with `n = 0`, if condition becomes true and recursion stops and control returns to `factorial(1)`. From now on every called function will return a value to the previous function in reverse order of function calls.

Example 3:

The program to calculates the power of a number using recursion.

Expected Output:

### 5 thoughts on “Recursive Function in C”

1. In example 1 if we replace the IF condition with a while loop than the program goes into a infinite loop. Why?

2. I thank God for giving you people.This is verymuch helpful and easy.Thank you dear teachers of OVERIQ.COM

3. Thanks…

4. This is one of the most helpful resources I’ve read on recursion up to this point. Keep up the good work.