11.1 – Recursion – introduction

by subbu on December 7, 2013

Recursion in C language:

Executing a statement or multiple statements repeatedly is called a loop or iteration. We have been using iteration statements in the places where statement(s) need to be executed repeatedly.
We can build iterations even by making a function calling itself. Let us see a simple example

#include<stdio.h>
int main()
{
 printf("Hello World\t");
 main(); /* recursive call */
 return 0;
}

Output:
Hello World   Hello World . . . . .

recursion with main

Here execution starts from the main() as the entry point to any C program is main(). The printf() statement prints “Hello World”. Next statement to printf() statement is “main();”, which calls the main() and sends the control to the beginning of main for the second time. Here calling main() itself forms an infinite loop and prints “Hello World” continuously.

We need a termination condition to build a limited loop using recursion. We can use a combination of counter variable and “if selection statement” to build limited loop using recursion. We will see an example of such limited loop here

#include<stdio.h>
int i=1;          /* counter variable */
int main()
{
 printf("Hello world\n");
 i++;
 if(i<=5)        /* termination condition   */
   main();       /* recursive call to main() */
 return 0;
}

Output:
Hello world
Hello world
Hello world
Hello world
Hello world

Here “Hello World” is printed and “i” is incremented for every recursive call. Recursion continue as long as i<=5 and stops when “i” becomes 6.
Here “i” is declared as a global variable because it must keep value for the next iteration.

Specification: Print 1 to 10 natural numbers

#include<stdio.h>
int main()
{
 static int i=1;
 printf("%5d",i);
 i++;
 if(i<=10)
   main();       /* recursive call */
 return 0;
}

Output:
1    2    3    4    5    6    7    8    9   10

The value of “i” is printed and incremented for every recursive call. Recursion continues as long as i<=10 and stops when “i” becomes 10.
Here counter variable “i” is declared as a static variable rather global variable to keep its value for the next iteration

Some times, unexpected things may happen with recursion. We will realize the fact with the following example, which prints the sum of 1 to 3 natural numbers.

#include<stdio.h>
int main()
{
 static int i,n=3,sum;
 if(i++<=n)        /*  termination condition */
 {
   sum=sum+i;
   main();            /* recursive call */
 }
 /* exit point */
 printf("Sum of 1 to 3 numbers %d\n",sum);
 return 0;
}

Output:
Sum of 1 to 3 numbers 6
Sum of 1 to 3 numbers 6
Sum of 1 to 3 numbers 6
Sum of 1 to 3 numbers 6

Recursive main() 1 to 3

If we think it as a loop, “Sum of 1 to 3 numbers 6” must print only once but, executed for four times even after the completion of recursion.
We can get the fact, if we think it as a function call rather a loop.
We know that, if a function calls another function, control comes back to caller once the execution of callee is completed.
The same way once the condition is false then control un-winds the functions and terminates one by one. While un-winding, printf() is executed for 4 times. As the “sum” is a static variable and common to all, its value “6” is printed for 4 times.
It can be rectified by separating recursive function and caller.

#include<stdio.h>
int main()
{
 int s;
 s=sum(3);
 printf("Sum of 1 to 3 numbers %d",s);
 return 0;
}
int sum(int n)
{
 int sm;
 if(n==1) /* termination statement */
   return 1;
 sm=n+sum(n-1);
 return sm;
}

Output:
Sum of 1 to 3 numbers 6

Recursion 1to3

Here the sum() function is sending n-1 as argument for every recursive call. It happens as long as n is not 1. If n==1 then recursion terminates and start returning “sm” to the callers.

sum(3) is called, n==1 is false, so calls 3+sum(2)
sum(2) is called, n==1 is false, so calls 2+sum(1)
sum(1) is called, n==1 is true, so return 1 to the caller

While unwinding, returning value of one function would be added to “n” of caller and assigns to “sm”, which would be returned to its caller as the result.

sum(1) return 1
sum(2) returns 2+sum(1) that is 2+1 is 3
sum(3) returns 3+sum(2) that is 3+3 is 6
Finally 6 is assigned to s of main(), that would be printed as output.

Conclusion:
Recursion is a process of building a loop by calling a function itself. A terminating condition is set to build limited number of iterations. The process of forwarding function call in recursion is called winding and returning control back on returning value is called unwinding.

Previous post:

Next post: