Recursive Function in C

In C, a function can call itself. This process is known as recursion. And a function that calls itself is called as the 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 simply 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) or (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 12 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 again the control again passes to level 3 rec() function with a formal argument of 3. The printf() statement in line 12 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 != 0factorial(5) calls factorial(4)
since 4 != 0factorial(4) calls factorial(3)
since 3 != 0factorial(3) calls factorial(2)
since 2 != 0factorial(2) calls factorial(1)
since 1 != 0factorial(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:

3 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?

Leave a Comment