遞迴

Recursion

Data Structures

Carrano © Data Abstraction and Problem Solving with C++, 5th ed.
 Objectives
Data Structures

Upon completion you will be able to:

 Explain the difference between iteration and
recursion
Determine when recursion is an appropriate
solution
Write simple recursive functions

Gilberg & Forouzan© Data Structures: A Pseudocode Approach with C, 2nd ed. P. 2
 Recursive Functions
Data Structures

Factorial
Greatest Common Divisor
Search in Array
Fibonacci series
Combinatorial numbers
Towers of Hanoi

P. 3
 Recursive Solutions
Data Structures

Recursion is an extremely powerful problem-solving

technique
– Breaks problem into smaller identical problems
– An alternative to iteration, which involves loops
A binary search is recursive
– Repeatedly halves the data collection and searches
the one half that could contain the item
– Uses a ___________________ strategy

P. 4
 Binary Search
Data Structures

A high-level binary search

binarySearch(in anArray:ArrayType, in value:ItemType)
if (anArray is of size 1)
Determine if anArray’s item is equal to value
else
{ Find the midpoint of anArray
Determine if the midpoint of anArray is equal to value
Determine which half of anArray contains value

if (value is in the first half of anArray)

binarySearch(first half of anArray, value)
else
binarySearch(second half of anArray, value)
} P. 5
 Binary Search
Data Structures

Implementation issues:
1. How will you pass “half of anArray” to the
recursive calls to binarySearch?
2. How do you determine which half of the array
contains value?
3. What should the base case(s) be?
4. How will binarySearch indicate the result of
the search?

P. 6
 Recursive Solutions
Data Structures

Facts about a recursive solution

– A recursive function calls itself
– Each recursive call solves an identical, but smaller,
problem
– The solution to at least one smaller problem— the
base case —is known
– Eventually, one of the smaller problems must be
the base case; reaching the base case enables the
recursive calls to stop

P. 7
 Recursive Solutions
Data Structures

Four questions for constructing recursive solutions

1. How can you define the problem in terms of a
smaller problem of the same type?
2. How does each recursive call diminish the
size of the problem?
3. What instance of the problem can serve as the
base case?
4. As the problem size diminishes, will you
reach this base case?

P. 8
 The Factorial of n
Data Structures

Problem
– Compute the factorial of an integer n
An iterative definition of factorial(n)
factorial(n) = n * (n – 1) * (n – 2) * … * 1
for any integer n > 0
factorial(0) = 1
A recursive definition of factorial(n)
factorial(n) = 1 if n = 0
= n * factorial(n–1) if n > 0
P. 9
 The Factorial of n
Data Structures

/** Computes the factorial of the nonnegative integer n.

* @pre n must be greater than or equal to 0.
* @post None.
* @return The factorial of n; n is unchanged. */
int fact(int n)
{
if (n == 0)
return 1;
else
return n * fact(n-1);
} // end fact
P. 10
 A Recursive Valued Function:
The Factorial of n
Data Structures

Box trace
– A systematic way to trace the actions of a recursive
function
– Each box roughly corresponds to an activation
record
– Contains a function’s local environment at the time
of and as a result of the call to the function
Input arguments, local variable
Recursive call
Return value
P. 11
 Box trace
Data Structures

fact(3) n=3 n=2

A: fact (n-1) = ?2 A: fact (n-1) = ?1
return ?6 return ?2

n=1 n=0
A: fact (n-1) = ?1 return 1
return ?1

P. 12
 A Recursive void Function:
Writing a String Backward
Data Structures

Problem
– Given a string of characters, write it in reverse order
Recursive solution
– Each recursive step of the solution diminishes by 1
the length of the string to be written backward
– Base case: write the empty string backward

P. 13
 Writing a String Backward
Data Structures

/** Writes a character string backward.

* @pre The string s contains size characters,
* where size >= 0.
* @post None.
* @param s The string to write backward.
* @param size The length of s. */
void writeBackward(string s, int size)
{
if (size > 0)
{ // write the last character
cout << [Link](size-1, 1);
P. 14
 Writing a String Backward
Data Structures

void writeBackward(string s, int size)

{
if (size > 0)
{ // write the last character
cout << [Link](size-1, 1);

// write the rest of the string backward

writeBackward(s, size-1); // Point A
} // end if

// size == 0 is the base case → do nothing

} // end writeBackward
P. 15
 Box trace
Data Structures

‘t’ ‘a’ ‘c’

I. s = ‘cat’ s = ‘cat’ s = ‘cat’ s = ‘cat’

size = 3 size = 2 size = 1 size = 0

‘c’ ‘a’ ‘t’

II. s = ‘cat’ s = ‘at’ s = ‘t’ s is empty

‘c’ ‘a’ ‘t’

III. s = ‘cat’ s = ‘at’ s = ‘t’ s is empty

P. 16
 Writing a String Backward
Data Structures

void writeBackward2(string s, int size)

{
if (s is empty) // the base case - do nothing
else
{
II. write the first character of s
writeBackward2(s minus its first character); // Point A
III. write the first character of s
} // end else
} // end writeBackward

P. 17
Writing an Array Backward
Data Structures

P. 18
Practice 1-1
Data Structures

 Given two natural numbers a and b, where a > b, write

a recursive function to compute the sum of all the
integers from a to b, inclusively.

P. 19
Practice 1-1: Solution
Data Structures

P. 20
 Recursive Solution
Data Structures

Four questions/steps
1. Define the problem in terms of smaller problems
2. See if a recursive call decreases the problem size
3. Find a complete set of ____________
4. Every time it will always reach a base case

P. 21
 Greatest Common Divisor
Data Structures

Problem
– Compute the GCD of two nonnegative integers x
and y
A recursive definition of GCD
gcd1(x, y) = x if y = 0
= gcd1(x, y mod x) if y > x
= gcd1(y, x mod y) otherwise

P. 22
 Practice 1-2
Data Structures

Another recursive definition of GCD

gcd2(x, y) = y if x mod y = 0
= gcd2(y, x mod y) otherwise

 Draw two box traces for the recursive functions based

on gcd1 and gcd2 with x=9, y=6. Which one is more
efficient (less recursive calls)?

P. 23
Practice 1-2: Solution
Data Structures

P. 24
 Binary Search with an Array
Data Structures

/** Searches the array anArray[first] through anArray[last]

* for value by using a binary search.
* @pre 0 <= first, last <= SIZE - 1, where SIZE is the
* maximum size of the array, and anArray[first] <=
* anArray[first + 1] <= ... <= anArray[last].
* @param anArray The array to search.
* @param first The low index to start search from.
* @param last The high index to stop searching at.
* @param value The search key.
* @return If value is in anArray, the function returns the
* index of the array item that equals value;
* otherwise the function returns -1. */ P. 25
 Binary Search with an Array
Data Structures

int binarySearch(const int anArray[], int first, int last, int value)
{
int index;
if (first > last)
index = -1; // value not in original array
else
{ // Invariant: If value is in anArray,
// anArray[first] <= value <= anArray[last]
int mid = ________________;
if (value == anArray[mid])
index = mid; // value found at anArray[mid]
P. 26
 Binary Search with an Array
Data Structures

else if (value < anArray[mid])

// point X
index = binarySearch(anArray, first, mid-1, value);

else
// point Y
index = binarySearch(anArray, ________, last, value);
} // end if
return index;
} // end binarySearch

P. 27
Finding the Largest Item in an Array
Data Structures

A recursive solution
if (anArray has only one item)
maxArray(anArray) is the item in anArray
else if (anArray has more than one item)
maxArray(anArray) is the maximum of
maxArray(left half of anArray) and
maxArray(right half of anArray)

P. 28
 Finding the Largest Item in an Array
Data Structures

Example

Try: write this algorithm P. 29

Finding the kth Smallest Item in an Array
Data Structures

The recursive solution proceeds by:

– Selecting a pivot item in the array
– Cleverly arranging, or partitioning, the items in
the array about this pivot item
– Recursively applying the strategy to one of the
partitions

P. 30
Finding the kth Smallest Item in an Array
Data Structures

Let:
kSmall(k, anArray, first, last) =
kth smallest item in anArray[first..last]

P. 31
 Finding the kth Smallest Item in an Array
Data Structures

Recursive Solution
kSmall(k, anArray, first, last)
= kSmall(k,anArray,first,pivotIndex-1)
if k < pivotIndex – first + 1

=p if k = pivotIndex – first + 1

= kSmall(k-______________, anArray,
pivotIndex+1, last) if k > pivotIndex – first + 1
Try: write this program
P. 32
 Iterative version of Binary Search
Data Structures

int iterativeBS(int anArray[], int key, int low, int high)

{ while (___________________)
{ mid = (low + high)/2;
if (anArray[mid] == key)
low = high;
else if (anArray[mid] < key)
low = mid + 1;
else high = mid - 1;
} // end while
if (low > high) return -1; // not found
else return mid;
} // end iterativeBS P. 33
 Iterative version of kSmall
Data Structures

int iterativeKSmall(int anArray[], int k, int size)

{ for (int i=0; i<k; i++)
for (int j=i+1; j<size; j++)
if (anArray[i] _______ anArray[j])
swap(anArray[i], anArray[j]);
return anArray[k-1];
} // end iterativeKSmall

P. 34
 After-class Exercise #1
Data Structures

 The Josephus problem (A mass suicide “game”)

1. n people numbered 1 to n, are sitting in a circle.
Starting at person 1, a handgun is passed.
2. After m passes, the person holding the gun commits
suicide, the body is removed, and the game continues
with the person who was sitting after the corpse
picking up the gun.
3. The survivor is tried for n-1 counts of manslaughter.
– Example: if m=2 and n=5 , the order is 2,4,1,5➔3.

P. 35
 After-class Exercise #1
Data Structures

 The Josephus problem

1. Goal: write an “iterative” algorithm to solve it for
general values of m and n.
2. Goal: write a “recursive” algorithm to solve it for
general values of m and n.
– Pseudo-codes only (as clear as possible)

P. 36