Module 7 – part 3 – Recursion
BITS Pilani
Pilani Campus
Department of Computer Science & Information Systems
Module Overview
• Recursion
• Recursive Functions
• Examples
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
BITS Pilani
Pilani Campus
Recursion
Recursion
• Recursion is the process of defining something in terms of
itself, and is sometimes called circular definition.
• A recursive process is one in which objects are defined in
terms of other objects of the same type.
• The entire class of objects can then be built up from a few
initial values and a small number of rules.
• Ex: Pingala sequence? - mātrāmeru
(Fibonacci Number series)
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
BITS Pilani
Pilani Campus
Recursive Functions
Recursive functions
• A recursive function is one which calls itself (repeatedly)
• Recursive functions are useful in evaluating certain types of
mathematical function. (we’ll see examples)
Simple Example:
main()
{
printf(“This is an example of recursive function”);
main();
}
When this program is executed. The line is printed repeatedly and
indefinitely. We might have to abruptly terminate the execution.
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Recursive functions contd..
• Solves a problem by calling a copy of itself to work on a
smaller problem.
• It is important to ensure that the recursion terminates.
Recursive vs iterative code:
• Recursive code is generally shorter and easier to write than
iterative code
• Solution to some problems are easier to formulate recursively
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Factorial Calculation
long int fact(int n) /* iterative */
{
int t, ans;
ans = 1;
for(t=1; t<=n; t++)
ans = ans*t;
return(ans);
}
long int factr(int n) /* recursive */
{
int ans;
if(n==1) Base case
return(1);
ans = n*factr(n-1);
return(ans); Recursive call
}
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Power function (Calculate non
negative power of a number)
double power(double val, unsigned pow)
{
if(pow == 0) /*pow(x, 0) returns 1*/
return(1.0);
else Base case
return(val*power(val, pow-1));
}
Recursive call
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Recursive Version of
Fibonacci Series
int fib(int num) /*Fibonacci value of a
number */
{
switch(num)
Base cases
{ case 0: return(0);
break;
case 1: return(1);
break;
default: /*Including recursive
calls */
return(fib(num - 1) + fib(num - 2));
break;
}
}
Recursive call
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Analysis
Input Value Number of time fib is called
0 1
1 1
2 3
3 5
4 9
5 15
6 25
7 41
8 67
9 109
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
How recursive functions
work???
• When a function calls itself, a new set of local variables and
parameters are allocated storage on the stack, and the function
code is executed from the top with these new variables.
• A recursive call does not make a new copy of the function. Only
the arguments are new.
• As each recursive call returns, the old local variables and
parameters are removed from the stack and execution resumes
at the point of the function call inside the function.
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Recursive Call Stack
(Example)
factr(4)
long int factr(int n) {
int ans;
if(n==1)
return(1); factr(2)
answer = n*factr(n-1);
return(ans); factr(3) factr(3)
} factr(4) factr(4) factr(4)
factr(1)
factr(2) factr(2)
factr(3) factr(3) factr(3)
factr(4) factr(4) factr(4) factr(4)
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Another Example
int main()
{
static int i=5;
if (--i){
printf("%d ",i);
main();
}
}
4321
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Cons of recursion
• No significant reduction in code size as well as no
improvement in memory utilization.
• Also, the recursive versions of most routines may execute a
bit slower than their iterative equivalents because of the
overhead of the repeated function calls.
• In fact, many recursive calls to a function could cause a stack
overrun.
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Pros of recursion
• The main advantage to recursive functions is that you can use
them to create clearer and simpler versions of several
algorithms.
• For example, the MergeSort and the Quicksort (two popular
sorting techniques) are quite difficult to implement in an
iterative way. Also, some problems, especially ones related to
artificial intelligence, lend themselves to recursive solutions.
• Finally, some people seem to think recursively more easily
than iteratively.
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
Precaution
• When writing recursive functions, you must have an if
statement somewhere to force the function to return without
the recursive call being executed.
• If you don't, the function will never return once you call it.
Dept. of Computer Science & Information Systems, BITS Pilani, Pilani Campus
BITS Pilani
Pilani Campus
Thank you
Q&A