1. Home
2. C Programming Tutorial
3. Recursive Function in C

Recursive Function in C

Last updated on July 27, 2020

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#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:

1
2
3
4
5
6

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) 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.

"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 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.

"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() 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.

"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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#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:

1
2

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#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:

1
2
3

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