Lecture 3: Recursion

Recursion
A function is said to be recursively defined, if a function
containing either a Call statement to itself or a Call statement
to a second function that may eventually result in a Call
statement back to the original function.

 A recursive function must have the following properties:

1. There must be certain criteria, called base criteria for which the function
does not call itself.
2. Each time the function does call itself(directly or indirectly), the argument
of the function must be closer to a base value.
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!
Example 1: factorial function

In general, we can express the factorial function as follows:

n! = n * (n-1)!

The factorial function is only defined for positive integers. So we

should be a bit more precise:
if n<=1, then n! = 1
if n>1, then n! = n * (n-1)!
 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
 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
 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:

Iterative solution
Recursive solution
int fac(int numb){
int fac(int numb){
int product=1;
if(numb<=1)
return 1; while(numb>1){
else product *= numb;
return numb*fac(numb-1); numb--;
} }
return product;
}
Recursion

To trace recursion, recall that function calls operate as a

stack – the new function is put on top of the caller

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
If we use iteration, we must be careful not to create an infinite loop by
accident:

for(int incr=1; incr!=10;incr+=2)

...

int result = 1;
while(result >0){
...
result++;
}
Recursion

Similarly, if we use recursion we must be careful not to create an

infinite chain of function calls:
int fac(int numb){
return numb * fac(numb-1);
}
No termination
Or:
condition
int fac(int numb){
if (numb<=1)
return 1;
else
return numb * fac(numb+1);
}
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

• 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
Example 2: Fibonacci numbers
• 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);
 Example 3: Fibonacci numbers
//Calculate Fibonacci numbers using recursive function.
//A very inefficient way, but illustrates recursion well

int fib(int number)

{
if (number == 0) return 0;
if (number == 1) return 1;
return (fib(number-1) + fib(number-2));
}
Fibonacci number w/o recursion

//Calculate Fibonacci numbers iteratively

//much more efficient than recursive solution

int fib(int n)
{
int f[n+1];
f[0] = 0; f[1] = 1;
for (int i=2; i<= n; i++)
f[i] = f[i-1] + f[i-2];
return f[n];
}
Example 3: Binary Search

• Search for an element in an array

• Sequential search
• Binary search
• Binary search
• Compare the search element with the middle
element of the array
• If not equal, then apply binary search to half of
the array (if not empty) where the search
element would be.
 Binary Search with Recursion

// Searches an ordered array of integers using recursion

int bsearchr(const int data[], // input: array
int first, // input: lower bound
int last, // input: upper bound
int value // input: value to find
)// output: index if found, otherwise return –1

{ int middle = (first + last) / 2;

if (data[middle] == value)
return middle;
else if (first >= last)
return -1;
else if (value < data[middle])
return bsearchr(data, first, middle-1, value);
else
return bsearchr(data, middle+1, last, value);
}
Binary Search
int main() {
const int array_size = 8;
int list[array_size]={1, 2, 3, 5, 7, 10, 14, 17};
int search_value;

cout << "Enter search value: ";

cin >> search_value;
cout << bsearchr(list,0,array_size-1,search_value)
<< endl;

return 0;
}
Binary Search w/o recursion

// Searches an ordered array of integers

int bsearch(const int data[], // input: array
int size, // input: array size
int value // input: value to find
){ // output: if found,return
// index; otherwise, return -1

int first, last, upper;

first = 0;
last = size - 1;
while (true) {
middle = (first + last) / 2;
if (data[middle] == value)
return middle;
else if (first >= last)
return -1;
else if (value < data[middle])
last = middle - 1;
else
first = middle + 1;
}
}
Example 4: Towers of Hanoi

1
2
3
A B C

• Only one disc could be moved at a time

• A larger disc must never be stacked above a smaller one
• One and only one extra needle could be used for intermediate storage of
discs
Towers of Hanoi

• From the moves necessary to transfer one, two, and three disks, we
can find a recursive pattern - a pattern that uses information from
one step to find the next step.

• If we want to know how many moves it will take to transfer 64 disks

from post A to post C, we will first have to find the moves it takes to
transfer 63 disks, 62 disks, and so on.
a) The initial state; b) move n - 1 disks from A to C
c) move one disk from A to B; d) move n - 1 disks from C to B
Towers of Hanoi

• The recursive pattern can help us generate more numbers to

find an explicit (non-recursive) pattern. Here's how to find the
number of moves needed to transfer larger numbers of disks
from post A to post C, when M = the number of moves needed
to transfer n-1 disks from post A to post C:
• for 1 disk it takes 1 move to transfer 1 disk from post A to post
C;
• for 2 disks, it will take 3 moves: 2M + 1 = 2(1) + 1 = 3
• for 3 disks, it will take 7 moves: 2M + 1 = 2(3) + 1 = 7
• for 4 disks, it will take 15 moves: 2M + 1 = 2(7) + 1 = 15
• for 5 disks, it will take 31 moves: 2M + 1 = 2(15) + 1 = 31
• for 6 disks... ?
Towers of Hanoi
Number of Disks (n) Number of Moves

1 21 - 1 = 2 - 1 = 1
2 22 - 1 = 4 - 1 = 3 3
23 - 1 = 8 - 1 = 7
4 24 - 1 = 16 - 1 = 15
5 25 - 1 = 32 - 1 = 31
6 26 - 1 = 64 - 1 = 63
• So the formula for finding the number of steps it takes to
transfer n disks from post A to post C is:
2 n- 1
Binomial coefficient

• Given a non-negative integer n and an integer k, the binomial

coefficient is defined to be the natural number

• Example: