### Chapter 8 Recursion

```Chapter 8 Recursion
§8.1 Introduction
§8.2 Methodology of Recursion Design
§8.3 Recursion vs. Iteration
§8.4 Case Studies
013225445X
1
Objectives




To know the concept of recursive function and the
benefits of using recursion
To learn the method of solving problems using
recursive functions
To learn the use of overloaded helper function to
derive a recursive function
To understand the relationship and difference
between recursion and iteration.
013225445X
2
§8.1 Introduction

Computing Factorial
Factorial in mathematics:
f(n) = n!
= 1*2*..*n
1
if n=0
=
n*(n-1)! if n>0

Recursive Call!
Factorial in C++
int factorial(int n){
int result;
if (n==0)
result =1;
else
result = n * factorial(n-1);
return result;
}

013225445X
3
Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);
factorial(3) =
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * ( 2 * (1 * factorial(0)))
= 3 * ( 2 * ( 1 * 1)))
= 3 * ( 2 * 1)
=3*2
=6
013225445X
4
Trace Recursive Factorial
return 24 to caller
factorial(4)
Step 0: execute factorial(4)
Step 9: return 24
for factorial(0)
4*factorial(3)
Step 1: execute factorial(3)
Step 8: return 6
3*factorial(2)
2*factorial(1)
Step 6: return 1
Space Required
for factorial(1)
Space Required
Step 2: execute factorial(2)
Step 7: return 2
Space Required
Step 3: execute factorial(1)
1*factorial(0)
Step 4: execute factorial(0)
for factorial(2)
Space Required
for factorial(3)
Space Required
for factorial(4)
Step 5: return 1
return 1
013225445X
5
Recursive Function

Recursive Function


A function with recursive call
Recursive call

A function calls itself, directly or indirectly
f( ){
……
f( );
……
}
f1( ){
……
f2( );
……
}
f2( ){
……
f1( );
……
}
013225445X
6
Fibonacci Numbers
Finonacci series: 0 1 1 2 3 5 8 13 21 34 55 89 …
indices: 0 1 2 3 4 5 6 7
8
9
10 11 …
0,
if i = 0
fib(i) = 1,
if i = 1
fib(n -1) + fib(n -2), if i >=2
fib(3) = fib(2) + fib(1)
= (fib(1) + fib(0)) + fib(1)
ComputeFibonacci
= (1 + 0) +fib(1)
= 1 + fib(1)
=1+1
Run
=2
013225445X
7
Fibonacci Numbers
fib(4)
17: return fib(4)
0: call fib(4)
return fib(3) + fib(2)
11: call fib(2)
10: return fib(3)
1: call fib(3)
16: return fib(2)
return fib(2) + fib(1)
7: return fib(2)
2: call fib(2)
9: return fib(1)
return fib(1) + fib(0)
return fib(1) + fib(0)
8: call fib(1)
return 1
13: return fib(1)
return 1
14: return fib(0)
12: call fib(1)
15: return fib(0)
return 0
5: call fib(0)
4: return fib(1)
3: call fib(1)
return 1
6: return fib(0)
return 0
013225445X
8
§8.2 Methodology of Recursion Design

Characteristics of Recursion

Different cases using selection statement

One or more base cases (the simplest case)


To stop recursion
Every recursive call reduces the original problem

To bring it increasingly closer to and eventually to be the base
case
013225445X
9
Problem Solving Using Recursion

General – thinking recursively


Divide and conquer
Sub-problems resemble the original
void nPrintln(char * msg, int times) {
if (times >= 1) {
cout << msg << endl;
nPrintln(msg, times - 1);
}
}
bool isPalindrome(const char * const s) {
if (strlen(s) <= 1) return true;
else if (s[0] != s[strlen(s) - 1]) return false;
else
return isPalindrome(substring(s, 1, strlen(s) - 2));
} 013225445X
10
Problem Solving Using Recursion


Specific – making use of recursive helper function
Recursive helper function


A recursive function with additional parameters to
reduce the problem
Especially useful for functions involving strings/arrays
bool isPalindrome(const char * const s, int low, int high) {
if (high <= low) return true;
else if (s[low] != s[high]) return false;
else return isPalindrome(s, low + 1, high - 1);
}
bool isPalindrome(const char * const s) {
return isPalindrome(s, 0, strlen(s) - 1);
}
013225445X
11
§8.3 Recursion vs. Iteration

Negative aspects of recursion


Recursion  Iteration


High cost in both time and memory
Any recursive function can be converted to nonrecursive (iterative) function
When to use recursion? Depending on the
problem.

Recursion is suitable for “recursive” problems
013225445X
12
Recursion vs. Iteration

f(n)= n!
int factorial(int n){
int result;
int i;
for(i=1;i<=n;i++)
result *= i;
return result;
}
int factorial(int n){
int result;
if(n==0) result =1;
else result = n*factorial(n-1);
return result;
}
013225445X
13
Recursion vs. Iteration
f(n) = 0
n=0
1
n=1
f(n-1)+f(n-2) n>1
int fib (int n) {
int result, i, pre1, pre2 ;
result = 0; i =2; pre2 = 1 ;
while (i<=n) {
pre1 = pre2 ;
pre2 = result ;
result = pre1 + pre2;
i++;
}
return result;
int fib (int n){
int result;
if (n==0) result =0;
else if (n==1) result =1;
else
result = fib (n-1)+ fib (n-2);
return result;
}
}
013225445X
14
§8.4 Case Studies

Recursive Selection Sort


Find the largest number in the list and swaps it with
the last number.
Ignore the last number and sort the remaining smaller
list recursively.
RecursiveSelectionSort
013225445X
15
Recursive Binary Search



If the key is less than the middle element,
recursively search the key in the first half of the
array.
If the key is equal to the middle element, the
search ends with a match.
If the key is greater than the middle element,
recursively search the key in the second half of
the array.
RecursiveBinarySearch
013225445X
16
Towers of Hanoi




There are n disks labeled 1, 2, 3, . . ., n, and three
towers labeled A, B, and C.
No disk can be on top of a smaller disk at any
time.
All the disks are initially placed on tower A.
Only one disk can be moved at a time, and it must
be the top disk on the tower.
013225445X
17
Towers of Hanoi
1
A
B
C
A
3
A
B
B
B
C
A
4
C
A
6
A
2
B
C
5
B
C
A
B
C
7
C
A
B
1. 把n-1个盘从A搬到B，借助C
2. 把A上剩下的最大的一个盘搬到C
3. 再把n-1个盘从B搬到C，借助A
4. 当n==1时，直接从A搬到C即可
C
TowersOfHanoi
Run
013225445X
18







void print_permutation(前缀序列A，集合S)
{
if (S为空) 输出序列A;
else 按照从小到大的顺序依次考虑S的每个元素v
{
print_permutation(在A的末尾填加v后得到的新序列, S-{v});
}
}
013225445X
19

void print_permutation(int n, int a[], int cur)
{
int i, j;
if (cur==n) //递归边界
{
for(int i=0;i<n;i++) printf("%d", a[i]);
printf("\n");
}
else for(int i=0;i<n;i++) //尝试在a[cur]中填各种整数i
{
int ok = 1;
for (j=0;j<cur;j++)
if (a[j]==i) ok = 0; //如果i已经在a[0]~a[cur-1]中出现，则不能再选
if (ok) {
a[cur] = i;
print_permutation(n,a,cur+1); //递归调用
}
}
}
20
013225445X
Summary



Concept of recursion
Design of recursive functions
Recursion vs. iteration