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:

int main()
{
    callme();
    ...
    return 0;
}

void rec()
{
    statement 1;
    ...
    rec();
}

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.

int main()
{
    callme();
}

void callme()
{
    if(base_condition)
    {
        // terminating condition
    }
    statement 1;
    ...
    callme();
}

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.

OK Enough theory, Let's take an example:

Example 1:

#include<stdio.h>
void rec();

int main()
{
     rec(1);

    // signal to operating system program ran fine
    return 0;
}

void rec(int n)
{
    printf("Winding phase: Level = %d\n", n);

    if(n<3)
    {
        rec(n+1);
    }

    printf("Unwinding phase: Level = %d\n", n);
}

Expected Output:

Winding phase: Level = 1
Winding phase: Level = 2
Winding phase: Level = 3
Unwinding phase: Level = 3
Unwinding phase: Level = 2
Unwinding phase: Level = 1

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.

"Winding phase: Level = 1"

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.

"Winding phase: Level = 2"

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.

"Winding phase: Level = 3"

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.

"Unwinding phase: Level = 3"

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.

"Unwinding phase: Level = 2"

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

Unwinding phase 3:

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

"Unwinding phase: Level = 1"

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.

#include<stdio.h>
int factorial(int n);

int main()
{
    int n;

    printf("Enter a number: ");
    scanf("%d", &n);

    printf("%d! = %d", n, factorial(n));

    // signal to operating system program ran fine
    return 0;
}

int factorial(int n)
{
    if(n == 0) // base condition
    {
        return 1;
    }

    else
    {
        return n * factorial(n-1);
    }
}

Expected Output:

Enter a number: 5
5! = 120

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.

#include<stdio.h>
int power(int base, int exp);
int main()
{
    int base, exp;

    printf("Enter base: ");
    scanf("%d", &base);

    printf("Enter exponent: ");
    scanf("%d", &exp);

    printf("%d ^ %d = %d", base, exp, power(base, exp));

    // signal to operating system everything works fine
    return 0;
}

int power(int base, int exp)
{
    if(exp == 0) // base condition
    {
        return 1;
    }

    else
    {
        return base * power(base, exp - 1);
     }
}

Expected Output:

Enter base: 4
Enter exponent: 3
4 ^ 3 = 64