Lesson 16: Recursion

Recursion simply means to call itself again and again. In C, we use recursion techniques to call a function again and again.


A function is said to be recursive if a statement inside that function call the same function again and again.



The best way to think of recursion is that each function call is a "process" being carried out by the computer. If we think of a program as being carried out by a group of people who can pass around information about the state of a task and instructions on performing the task, each recursive function call is a bit like each person asking the next person to follow the same set of instructions on some part of the task while the first person waits for the result.

At some point, we're going to run out of people to carry out the instructions. There needs to be a way to avoid this! To halt a series of recursive calls, a recursive function will have a condition that controls when the function will finally stop calling itself. The condition where the function will not call itself is termed the base case of the function. Basically, it will usually be an if-statement that checks some variable for a condition (such as a number being less than zero, or greater than some other number) and if that condition is true, it will not allow the function to call itself again. (Or, it could check if a certain condition is true and only then allow the function to call itself).

Common examples of where recursion is used :

• Walking recursive data structures such as linked lists, binary trees, etc.
• Exploring possible scenarios in games such as chess

Recursion always consists of two main parts. A terminating case that indicates when the recursion will finish and a call to itself that must make progress towards the terminating case.

Let us understand this technique with some example:

As we know, the factorial of a number is the product of all the integers between 1 and that number. For example, 4 factorial is 4 * 3 * 2 * 1. This can also be expressed as 4! = 4 * 3! where ‘!’ stands for factorial. Thus factorial of a number can be expressed in the form of itself. Hence this can be programmed using recursion.

Let us try to calculate factorial using Non-recursive code:

#include<stdio.h>

int factorial( int);
int main( )
{
int a, fact ;
printf ( "\nEnter any number " ) ;
scanf ( "%d", &a ) ;
fact = factorial ( a ) ;
printf ( "Factorial value = %d", fact ) ;
}
/* Non -recursive code below*/
int factorial ( int x )
{
int fact= 1, i ;
for ( i = x ; i >= 1 ; i-- )
fact= fact* i ;
return ( fact ) ;
}

C compiler to run above code:https://goo.gl/bzuHcQ

And here is the output...
Enter any number 5
Factorial value = 120



 Try to read the above code twice or thrice till you understand the logic of the program properly. Recursive factorial function can be understood only if you are through with the above logic.



Let us use the recursive technique to calculate the factorial of a number:

Below is just function only:

int factorial ( int x )
{
int fact ;
if ( x == 1 )
return ( 1 ) ;
else
fact= x * rec ( x - 1 ) ;
return ( fact ) ;
}

Let us understand the above  code using recursive function

 In the first run when the number entered through scanf( ) is 1, let us see what action does rec( ) take. The value of a (i.e. 1) is copied into x. Since x turns out to be 1 the condition if ( x == 1 ) is satisfied and hence 1 (which indeed is the value of 1 factorial) is returned through the return statement. 

When the number entered through scanf( ) is 2, the ( x == 1 ) test fails, so we reach the statement,

f = x * rec ( x - 1 ) ;

And here is where we meet recursion. How do we handle the expression x * rec ( x - 1 )? We multiply x by rec ( x - 1 ). Since the current value of x is 2, it is same as saying that we must calculate the value (2 * rec ( 1 )). We know that the value returned by rec ( 1 ) is 1, so the expression reduces to (2 * 1), or simply 2. Thus the statement, x * rec ( x - 1 ) ; evaluates to 2, which is stored in the variable f, and is returned to main( ), where it is duly printed as

Factorial value = 2

In case the value of a is 5, main( ) would call rec( ) with 5 as its actual argument, and rec( ) will send back the computed value.
 But before sending the computed value, rec(  ) calls rec( ) and waits for a value to be returned. It is possible for the rec( ) that has just been called to call yet another rec( ), the argument x being decreased in value by 1 for each of these recursive calls. 

We speak of this series of calls to rec( ) as being different invocations of rec( ). These successive invocations of the same function are possible because the C compiler keeps track of which invocation calls which. 


These recursive invocations end finally when the last invocation gets an argument value of 1, which the preceding invocation of rec( ) now uses to calculate its own f value and so on up the ladder. So we
might say what happens is, rec ( 5 ) returns ( 5 times rec ( 4 ), which returns ( 4 times rec ( 3 ),
which returns ( 3 times rec ( 2 ), which returns ( 2 times rec ( 1 ), which returns ( 1 ) ) ) ) )


Well, that is recursion for you in its simplest garbs. I hope you agree that it’s difficult to visualize how the control flows from one function call to another 


Assume that the number entered through scanf( ) is 3. Using below flow let’s visualize what exactly happens when the recursive function rec( ) gets called. 

Go through the flow carefully. The first time when rec( ) is called from main( ), x collects 3. From
here, since x is not equal to 1, the if block is skipped and rec( ) is called again with the argument ( x – 1 ), i.e. 2. 

This is a recursive call. Since x is still not equal to 1, rec( ) is called yet another time, with argument (2 - 1). This time as x is 1, control goes back to previous rec( ) with the value 1, and f is evaluated as 2.


Similarly, each rec( ) evaluates its f from the returned value, and finally 6 is returned to main( ). The sequence would be grasped better by following the arrows shown in flow. Let it be clear that while executing the program there do not exist so many copies of the function rec( ). These have been shown in the flow just to help you keep track of how the control flows during successive
recursive calls.