Lecture 18
In C, it is possible for the functions to call
themselves. A function is called ‘recursive’ if a statement within the body of
a function calls the same function. Sometimes called ‘circular definition’,
recursion is thus the process of defining something in terms of itself.
Let us now see a simple example of recursion.
Suppose we want to calculate the factorial value of an integer. 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.
However, before we try to write a recursive function for calculating factorial
let us take a look at the non-recursive function for calculating the factorial
value of an integer.
Work through the above program carefully, till
you understand the logic of the program properly. Recursive factorial function
can be understood only if you are thorough with the above logic.
Following is the recursive version of the
function to calculate the factorial value.
Let us understand this recursive factorial
function thoroughly. 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
Now perhaps you can see what would happen if
the value of a is 3, 4, 5 and so on.
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,
Assume that the number entered through scanf(
) is 3. Using the following figure let’s visualize what exactly happens
when the recursive function rec( ) gets called. Go through the figure
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 Figure. 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 figure just tohelp
you keep track of how the control flows during successive recursive calls.
Let’s take another simple example.
#include <stdio.h>
void recurse (int i);
void main(){
recurse
(0);
}
void recurse (int i){
if
(i<10){
recurse
(i+1);
printf(“%d”,i);
}
}
the recurse() is first called with 0. This is
recurse’s first activation. Since 0 is less than 10, recurse() then calls
itself with the value of i+1 (1). This is the second activation of the
function. This causes recurse() to call itself again with the value 2. this
process repeats until recurse () is called with the value 10. this causes
recurse(0 to return. Since it returns to the point of its call, it will execute
printf() statement in its previous activation and prints 9 and return. And that
continues up to printing 0.
Note that, this program does not have a
base-case, recursive-case feature of recursive problems. It only has one case.
Fibonacci number is a series of whole numbers
in which each number is the sum of the two preceding numbers. Beginning with 0
and 1, the sequence of Fibonacci numbers would be 0,1,1, 2, 3, 5, 8, 13, 21,
34, etc. using the formula n = n(-1) + n(-2), where the n(-1) means "the
last number before n in the series" and n(-2) refers to "the second
last one before n in the series.”
In computer programming, Fibonacci numbers give
a model for designing recursive
programming algorithms where the time
for any routine is the time within the routine itself, plus the time for the
recursive calls. Let’s take a look at
the program that finds the Fibonacci number.
#include<stdio.h>
long fib(long int);
void main ()
{
long int num,result;
{
long int num,result;
printf(“Enter Number: ”);
scanf(“%ld”, &num);
result=fib(num);
printf("The Fibonacci number of %ld is %ld",num,result);
}
long fib(long int n)
{
if(n==0 || n==1)
return;
result=fib(num);
printf("The Fibonacci number of %ld is %ld",num,result);
}
long fib(long int n)
{
if(n==0 || n==1)
return;
else
{
return fib(n-1) +fib(n-2);
}
}
{
return fib(n-1) +fib(n-2);
}
}
Recursion
vs Iteration
1. Both
iteration and recursion are based on control structure. Iteration uses a
repitation structure and recursion uses a selection structure.
2. Both
involves in a termination state checking.
3. Both can
be run infinitely. (which is of course not desirable)
4.
Recursion is expensive in case of memory and processing time than iteration.
5.
Recursion for many cases makes programs easier.
6.
Recursion is the style of stylish programmer. J
1 comments:
This is great blog! Keep it up. chemical wash aircon price
Post a Comment