C Programming Recursion

RECURSION

In C, any function can call another function. A function can even call itself! When a function calls
itself, it is making a recursive call. The word recursive means “having the characteristic of coming up
again, or repeating.” In this case, a function call is being repeated by the function itself. Recursion is a
powerful technique that can be used in place of iteration (looping).
Recursive solutions are generally less efficient than iterative solutions to the same problem.
However, some problems lend themselves to simple, elegant, recursive solutions and are exceedingly
cumbersome to solve iteratively.

What is a Recursion?
You may have seen a set of gaily-painted Russian dolls that fit inside one another. Inside the first
doll is a smaller doll, inside of which is an even smaller doll, inside of which is yet a smaller doll, and so
on. A recursive algorithm is like such a set of Russian dolls. It reproduces itself with smaller and smaller
examples of itself until a solution is found – that is, until there are no more dolls. The recursive algorithm
is implemented by using a function that makes recursive calls to itself.

Recursive Call - a function call in which the function being called is the same as the one
making the call.

If we were to write a function named getPower, which calculates the result of raising an integer X
to a positive power N, the formula for XN is

XN = X * X * X * X * . . . * X

N times

We could also write this formula as

XN = X * (X * X * . . . * X)

(N – 1) times

or even as

XN = X * X * (X * X * . . . * X)

(N – 2) times

1
C Programming Recursion

In fact, we can write formula most concisely as

XN = X * XN-1

This definition of XN is a classic recursive definition – that is, a definition given in terms of a
smaller version of itself.
XN is defined in terms of multiplying X times XN-1. How is XN-1 defined? Why, as X * XN-2, of
course! And XN-2 is X * XN-3; XN-3 is X * XN-4; and so on. In this example, “in terms of smaller versions of
itself” means that the exponent is decremented each time.
When does the process stop? When we have reached a case where we know the answer without
resorting to a recursive definition. In this example, it is the case where N equals 1: X1 is X. The case (or
cases) for which an answer is explicitly known is called the base case. The case for which the solution is
expressed in terms of a smaller version of itself is called recursive or general case. A recursive
algorithm is an algorithm that expresses the solution in terms of a call to itself, a recursive call. A recursive
algorithm must terminate; that is, it must have a base case.
The program below shows a recursive version of the getPower function with the base case and the
recursive call marked.

#include <stdio.h>

int getPower(int, int);

int main(void) {
int num, exp;

printf("Input number and exponent: " );

scanf("%d %d", &num, &exp);
printf("%d raised to the power %d is %d", num, exp, getPower(num, exp));
return 0;
}

int getPower(int x, int n) {

if (n == 1)
return x; // Base case
else
return x * getPower(x, n – 1); // Recursive case
}

Each recursive call to getPower can be thought of as creating a completely new copy of the
function, each with its own copies of the parameters x and n. The value of x remains the same for each
version of getPower, but the value of n decreases by one for each call until it becomes 1.
Let’s trace the execution of this recursive function with num equal to 2 and exp equal to 3. We use
a new format to trace recursive routines: we number the calls and then discuss what is happening in
paragraph form.
Call 1: getPower is called by main, with num equal to 2 and exp equal to 3. Within getPower, the
formal parameters x and n are initialized to 2 and 3, respectively. Because n is not equal to 1, getPower

2
C Programming Recursion

is called recursively with x and n – 1 as parameters. Execution of Call 1 pauses until an answer is sent
back from this recursive call.
Call 2: x is equal to 2 and n is equal to 2. Because n is not equal to 1, the function getPower is
called again, this time with x and n – 1 as parameters. Execution of Call 2 pauses until an answer is sent
back from this recursive call.
Call 3: x is equal to 2 and n is equal to 1. Because n equals 1, the value of x is to be returned. This
call to the function has finished executing, and the function return value (which is 2) is passed back to the
place in the statement from which the call was made.
Call 2: This call to the function can now complete the statement that contained the recursive call
because the recursive call has returned. Call 3’s return value (which is 2) is multiplied by x. This call to
the function has finished executing, and the function return value (which is 4) is passed back to the place
in the statement from which the call was made.
Call 1: This call to the function can now complete the statement that contained the recursive call
because the recursive call has returned. Call 2’s return value (which is 4) is multiplied by x. This call to
the function has finished executing, and the function return value (which is 8) is passed back to the place
in the statement from which the call was made. Because the first call (the non-recursive call in main) has
now completed, this is the final value of the function getPower.
This trace is summarized in the figure below. Each box represents a call to the getPower function.
The values for the parameters for that call are shown in each box.

Execution of getPower (2, 3)

getPower (2, 3)

Returns 8
x n
Call 1: 2 3

Returns 4
x n
Call 2: 2 2

Returns 2
x n
Call 3: 2 1

What happens if there is no base case? We have infinite recursion, the recursive equivalent of an
infinite loop. For example, if the statement

if (n == 1)

were omitted, getPower would be called over and over again.