Transcript Chapter 4 Methods

Chapter 17 Recursion (递归)
§17.1 Introduction
§17.2 Methodology of Recursion Design
§17.3 Recursion vs. Iteration
§17.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!
2
Factorial in C++
int factorial(int n){
int result;
if (n==0)
result =1;
else
result = n * factorial(n-1);
return result;
}

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
3
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
Step 3: execute factorial(1)
1*factorial(0)
Step 4: execute factorial(0)
Step 5: return 1
return 1
4
Space Required
for factorial(1)
Space Required
Step 2: execute factorial(2)
Step 7: return 2
Space Required
for factorial(2)
Space Required
for factorial(3)
Space Required
for factorial(4)
Recursive Function

Recursive Function


A function with recursive call
Recursive call

A function calls itself, directly or indirectly
f( ){
……
f( );
……
}
5
f1( ){
……
f2( );
……
}
f2( ){
……
f1( );
……
}
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(i -1) + fib(i -2), if i >=2
fib(3) = fib(2) + fib(1)
= (fib(1) + fib(0)) + fib(1)
= (1 + 0) +fib(1)
= 1 + fib(1)
=1+1
=2
6
ComputeFibonacci
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)
5: call fib(0)
4: return fib(1)
3: call fib(1)
return 1
7
6: return fib(0)
return 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
§17.2 Methodology of Recursion Design

Characteristics of Recursion

Different cases using selection statement

One or more base cases (the simplest case)


Every recursive call reduces the original problem

8
To stop recursion
To bring it increasingly closer to and eventually to be the base
case
Problem Solving Using Recursion

General – thinking recursively


9
Divide and conquer
Sub-problems resemble the original
void nPrintln(string msg, int times) {
if (times >= 1) {
cout << msg << endl;
nPrintln(msg, times - 1);
}
}
bool isPalindrome(const string 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));
}
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);
}
10
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
11
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
12
Towers of Hanoi




13
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.
Solution to Towers of Hanoi
Decompose the problem into three subproblems.
n-1 disks
n-1 disks
..
.
A
..
.
B
Original position
C
n-1 disks
..
.
A
B
C
Step 1: Move the first n-1 disks from A
to C recursively
A
B
C
Step2: Move disk n from A
to C
n-1 disks
..
.
A
B
C
Step3: Move n-1 disks from
C to B recursively
n  n-1  n-2  … 1,
14 move it directly!
Towers of Hanoi
1
A
B
C
A
3
A
B
B
B
C
A
A
B
C
5
B
C
A
B
C
7
C
A
B
1. 把n-1个盘从A搬到C，借助B
2. 把A上剩下的最大的一个盘搬到B
3. 再把n-1个盘从C搬到B，借助A
4. 当n==1时，直接从A搬到B即可
15
C
4
6
A
2
C
TowersOfHanoi
Eight Queens
queens[0]
0
queens[1]
4
queens[2]
7
queens[3]
5
queens[4]
2
queens[5]
6
queens[6]
1
queens[7]
3
bool isValid(int row, int column)
{
for (int i = 1; i <= row; i++)
if (queens[row - i] == column
|| queens[row - i] == column - i
|| queens[row - i] == column + i)
return false; // There is a conflict
return true; // No conflict
}
EightQueen
16
§17.3 Recursion vs. Iteration (迭代)

Negative aspects of recursion


Recursion  Iteration


Any recursive function can be converted to nonrecursive (iterative) function
When to use recursion? Depending on the
problem.

17
High cost in both time and memory
Recursion is suitable for “recursive” problems
Recursion vs. Iteration

f(n)= n!
int factorial(int n){
int result;
int i;
for(i=1;i<=n;i++)
result *= i;
return result;
}
18
int factorial(int n){
int result;
if(n==0) result =1;
else result = n*factorial(n-1);
return result;
}
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;
}
19
}
Summary



20
Concept of recursion
Design of recursive functions
Recursion vs. iteration
Homework Questions
1. Please write a recursive function to solve the
Sudoku problem.
2. How to find all possible solutions for the Eight
Queens problem?
 (Just for exercise by yourself. No need to
submitting it.)
21