Recursion
Recursion / Slide 2
Recursion
Recursion is the process of repeating items in a self-
similar way.
For instance, when the surfaces of two mirrors are exactly
parallel with each other the nested images that occur are a
form of infinite recursion
The most common application of recursion is in
mathematics and computer science, in which it refers
to a method of defining functions in which the function
being defined is applied within its own definition.
Specifically this defines an infinite number of
instances (function values)
Recursion / Slide 3
Recursion
In some problems, it may be natural to define
the problem in terms of the problem itself.
Recursion is useful for problems that can be
represented by a simpler version of the same
problem.
Example: the factorial function
6! = 6 * 5 * 4 * 3 * 2 * 1
We could write:
6! = 6 * 5!
Recursion / Slide 4
Example 1: factorial function
In general, we can express the factorial
function as follows:
n! = n * (n-1)!
Is this correct? Well… almost.
The factorial function is only defined for
positive integers. So we should be a bit more
precise:
n! = 1 (if n is equal to 1)
n! = n * (n-1)! (if n is larger than 1)
Recursion / Slide 5
factorial function
The C++ equivalent of this definition:
int fac(int numb){
if(numb<=1)
return 1;
else
return numb * fac(numb-1);
}
recursion means that a function calls itself
Recursion / Slide 6
factorial function
Assume the number typed is 3, that is, numb=3.
fac(3) :
3 <= 1 ? No.
fac(3) = 3 * fac(2)
fac(2) :
2 <= 1 ?
No.
fac(2) = 2 * fac(1)
fac(1) :
1 <= 1 ? Yes.
return 1 int fac(int numb){
fac(2) = 2 * 1 = 2 if(numb<=1)
return fac(2) return 1;
fac(3) = 3 * 2 = 6 else
return fac(3) return numb * fac(numb-1);
}
fac(3) has the value 6
Recursion / Slide 7
factorial function
For certain problems (such as the factorial function), a
recursive solution often leads to short and elegant code.
Compare the recursive solution with the iterative solution:
Recursive solution Iterative solution
int fac(int numb){ int fac(int numb){
if(numb<=1) int product=1;
return 1; while(numb>1){
else product *= numb;
return numb*fac(numb-1); numb--;
}
}
return product;
}
Recursion / Slide 8
Recursion
We have to pay a price for recursion:
calling a function consumes more time and memory than
adjusting a loop counter.
high performance applications (graphic action games,
simulations of nuclear explosions) hardly ever use recursion.
In less demanding applications recursion is an
attractive alternative for iteration (for the right
problems!)
Recursion / Slide 9
Recursion
If we use iteration, we must be careful not to
create an infinite loop by accident:
for(int incr=1; incr!=10;incr+=2)
...
Oops!
int result = 1;
while(result >0){
...
result++;
}
Oops!
Recursion / Slide 10
Recursion
Similarly, if we use recursion we must be
careful not to create an infinite chain of
function calls:
int fac(int numb){ Oops!
return numb * fac(numb-1); No termination
}
condition
Or:
int fac(int numb){
if (numb<=1)
return 1;
else
return numb * fac(numb+1);
}
Oops!
Recursion / Slide 11
Recursion
We must always make sure that the recursion
bottoms out:
A recursive function must contain at least one
non-recursive branch.
The recursive calls must eventually lead to a
non-recursive branch.
Recursion / Slide 12
Recursion
Recursion is one way to decompose a task into
smaller subtasks. At least one of the subtasks is
a smaller example of the same task.
The smallest example of the same task has a
non-recursive solution.
Example: The factorial function
n! = n * (n-1)! and 1! = 1
Recursion / Slide 13
How many pairs of rabbits can be produced from a
single pair in a year's time?
Assumptions:
Each pair of rabbits produces a new pair of offspring every
month;
each new pair becomes fertile at the age of one month;
none of the rabbits dies in that year.
Example:
After 1 month there will be 2 pairs of rabbits;
after 2 months, there will be 3 pairs;
after 3 months, there will be 5 pairs (since the following month
the original pair and the pair born during the first month will both
produce a new pair and there will be 5 in all).
Recursion / Slide 14
Population Growth in Nature
Leonardo Pisano (Leonardo Fibonacci = Leonardo, son of
Bonaccio) proposed the sequence in 1202 in The Book of the
Abacus.
Fibonacci numbers are believed to model nature to a certain
extent, such as Kepler's observation of leaves and flowers in
1611.
Recursion / Slide 15
Direct Computation Method
Fibonacci numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
where each number is the sum of the preceding
two.
Recursive definition:
F(0) = 0;
F(1) = 1;
F(number) = F(number-1)+ F(number-2);
Recursion / Slide 16
Recursion / Slide 17
Example 2: Fibonacci numbers
//Calculate Fibonacci
numbers using recursive
int fib(int number)
function. {
int fib(int);
int main() if (number == 0) return 0;
{// driver function
int count; else if (number == 1)
cout << " how many number you want to enter in
Fibonacci series "; return 1;
cin >> count;
for(int i=0;i<=count;i++) else return (fib(number-1)
{ + fib(number-2));
cout<< fib(i)<<endl; }
}
system("pause");
return 0;
}
The Handshake Problem
Recursion / Slide 18
• Let’s suppose you
shook hands with
everyone in this
class. How many
handshakes would
there be? Act it out
in your class,
starting with one
person and filling in
the table on the next
slide as you add
Recursion / Slide 19
The Handshake Table
# of People # of Handshakes
1 0
Make this 2 1
3 3
chart in your
journal and
look for any
patterns you
see after
showing 8
handshakes.
Recursion / Slide 20
The Handshake Table
# of
# of People
People #
# of
of Handshakes
Handshakes
11 00
22 11
33 33
4 6
5 10
6 15
7 21
8 28
Recursion / Slide 21
Ex. 3: The Handshake Problem
There are n people in a room. If each person
shakes hands once with every other person.
What is the total number h(n) of handshakes?
h(n) = h(n-1) + n-1 h(4) = h(3) + 3 h(3) = h(2) + 2 h(2) = 1
h(n): Sum of integer from 1 to n-1 = n(n-1) / 2