Recursion C

• Writing a recursive function.
• Execution of recursive functions.

A function calling itself is called a recursive function i.e. some statement in a function body gives a call to the same function.

Writing a recursive function
The concept of recursion and recursive function will be made clear by studying the example of factorial. Let us write a function to get the factorial of a number. The factorial of a number is the
product of all the integers between 1 and that number.

E.g. Factorial of 3, i.e. 3! = 3*2*1 = 6
Example:

/* program to find factorial of a number using recursion */

The statement
f = x * fact (x – 1) in the function fact is a recursive call. i.e. fact calls fact itself. Only the value of arguments passes each time varies.

The function calls itself repeatedly. This has to end somewhere. When writing recursive functions you must have a terminating condition in the function, to return, in the absence of which the program will go into infinite loop of calling itself.

In the above example

if (x = =1) return(1);

is the terminating condition. When the function fact is called by passing value ‘1’ as its argument it returns 1.

Execution of recursive functions
Let us see what happens on running this program
If the input given is 1:
The value of a = 1 is copied to x. The condition (x = = 1) is true hence ‘1’ is returned to the function main and printed there.

‘C’ needs to keep track of where to continue execution after return statement is encountered. This is achieved by using a ‘stack’ which holds the functions and the location from where execution is to resume. Let us consider the above program by giving input value of 3. The figure showing flow of the program and the stack contents will help understand the program.

Stacks are memory locations. Stack works on LIFO (last in first out) technique. i.e. Contents entered last are removed first.

If the input given is 3.

When function main() is executing main is put in the stack. Fact is called from main with a value of 3. fact(3) is added to stack. Fig(1)

In function fact(3) value of x is equal to 3. (x = = 1) is false hence f = 3 * fact(3 – 1)is executed i.e. fact(2) is called from fact(3). Fact(2) gets added to stack. Fig(2)

In function fact(2) value of x is equal to 2. (x = =1) is false hence f = 2 * fact(2 – 1) is executed i.e. fact(1) is called from fact(2). Fact(1) gets added to stack. Fig(3)

In function fact(1) value of x is equal to 1. (x = = 1) is true hence fact(1) returns value of 1. fact(1) is removed from stack. fig(4)

Now topmost function in stack is fact(2), so ‘C’ knows that it has to return to function fact(2) at the place it left i.e. at the statement f = 2 * fact(1). Here fact(1) is replaced by 1. Therefore f = 2. Next statements return(f) return value of 2. fact(2) is removed from stack. Fig(5)

Now topmost function in stack is fact(3). So ’C’ returns to function fact(3) at the place it left i.e. fact(3)at f = 3 * fact(2). fact(2) is replaced by 2. Hence f = 3 * 2 = 6. return(f) return value of 6. fact(3) is removed from stack. Fig(6)
Finally value 6 is returned to function main()