Transcript Course 6:Recursion - 天府学院数据结构精品课程

Data Structures(数据结构)
Course 6:Recursion
Vocabulary
Recursion(递归): a repetitive process in which an
algorithm call itself, that is recursive
algorithm.
Stack frame(栈帧）: 在栈中为参数、返回地址和局部变
量保留的一块内存区,必要时在过程
调用中使用。
Factorial(阶乘): the product of the integral values
from 1 to the number.
Fibonacci number(斐波纳契数列)
The towers of hanoi(汉诺塔)
西南财经大学天府学院
2
Highlights in this chapter
Factorial – A classical recursive case
How recursion works
Fibonacci number – Another recursion case
The towers of hanoi -- A classic recursive algorithms
西南财经大学天府学院
3
6-1 Factorial – A case study
Factorial(3) = 3*2*1=6
Factorial definition: the factorial of a number is
product of the integral values from 1 to the number.
Iteration algorithm definition
1
if n = 0
Factorial(n) =
n*(n-1)*(n-2)*…*3*2*1
Recursion algorithm
definition
if n > 0
Factorial(3) = 3* Factorial(2)
Factorial(3)=3*2 =6
Factorial(2) = 2* Factorial(1)
Factorial(2)=2*1 =2
Factorial(1) = 1* Factorial(0)
Factorial(1)=1*1 =1
Factorial(0) = 1
1
if n = 0
n*( Factorial(n-1))
if n > 0
Factorial(n) =
西南财经大学天府学院
4
Iterative factorial algorithm
Algorithm iterativeFactorial (val n
<integer>)
Calculates the factorial of a number
using a loop.
Pre n is the number to be raised
factorially
Return n! is returned
1 i=1
2 factN = 1
3 loop (i <= n)
1 factN = factN * i
2 i=i+1
4 end loop
5 return factN
end iterativeFactorial
Recursive factorial Algorithm
Algorithm recursiveFactorial (val n
<integer>)
Calculates the factorial of a number using
recursion
Pre
n is the number to be raised
factorially
Return n! is returned
1 if (n equal 0)
1 return 1
2 else
1 return (n * recursiveFactorial(n - 1))
3 end if
end recursiveFactorial
西南财经大学天府学院
5
When the power is called, the stackframe is
created. It contains four elements:
1. The parameters to be processed by the called
algorithm
2. The local variables in the calling algorithm
3. The return statement in the calling algorithm
4. The expression that is to receive the return
value
6-2 How recursion works
How any call works
Program testPower
1 Read (base, exp)
2 Result = power(base, exp)
3 Print (base * exp = result)
End testPower
Algorithm power (base <integer>,
exp < integer >)
1 Num = 1
2 Loop (exp >0)
1 num = num * base
2 exp = exp – 1
3 End loop
4 Return num
End testPower
西南财经大学天府学院
6
How recursion works
1. Parameters 5, 1
Stackframes for power(
1. Parameters 5, 2
2. Local Var none
3. Return to
testPower
4. Return value unknown
1. Parameters 5, 2
2. Local Var none
3. Return to
testPower
4. Return value 5 * 5
1. Parameters 5, 1
,
Algorithm power ( val base
2. <integer>,
Local Var none
2. Local Var none
to >) power 2.1
3. Return to
power 2.1
val exp3.
<Return
integer
4. Return value unknown
4. Return value 5 * 1
This algorithm computes the value of a
number,base, raised to1.the
power of an
Parameters
5, 2
1. Parameters 5, 2
2. Local Var none
2. Local Var none
exponent ,exp.
3. Return to
testPower
3. Return to
testPower
4. Return
value unknown
4. Return value unknown
Pre base is the number
to be raised
Post
value of base raised to power
5
exp computed
Calls Return
2
return value of base raised
to power exp
1. Parameters 5, 0
1. Parameters
5, 0
2. Local Var none
2.
Local
Var
none
returned
3. Return to
power 2.1
3. Return to
power 2.1
4. Return value 1
4. Return value unknown
1 If (exp equal 0)
1 return (1)
1. Parameters 5, 1
1. Parameters 5, 1
2 Else
2. Local Var none
2. Local Var none
3. Return to
power 2.1
3.
Return
to
power
2.1
1 return (base * power (base, exp – 1 ))
4. Return value unknown
4. Return value unknown
3 End if
End power
1. Parameters 5, 2
1. Parameters 5, 2
)
2. Local Var none
3. Return to
testPower
4. Return value unknown
西南财经大学天府学院
2. Local Var none
3. Return to
testPower
4. Return value unknown
7
Recursive factorial Algorithm
西南财经大学天府学院
8
6-3 Designing recursive algorithm
• The design methodology Factorial(0)
Every recursive algorithm have two elements:
base case – solve a part of the problem
general case -- reduce the size of the problem
n * Factorial(n-1)
• The rules for designing a recursive
algorithm
1. First ,determine the base case.
2. Then determine the general case.
3. Combine the base case and general case into an algorithm
• Limitation of recursion
1. Is the algorithm or data structure naturally suited to recursion?
2. Is the recursive solution shorter and more understandable?
3. Does the recursive solution run in acceptable time and space
limits?
西南财经大学天府学院
9
Design implementation reverse a linked list
We need to print the list in reverse but not have reverse
pointers:
pList
6
10
20
14
We print the list after
find the last node(20).
Algorithm printReverse ( val plist <pointer to
base
have found node>)
the last node(20).
that
is,wecase:
print node
data
as we back
Print singly
in reverse.
general
caseout: of
if not reach
thelinked
last list
node
, to find the next
Pre list has been built
recursion
node
Algorithm : print linked
Post list printed in reverse
1 reverse
If (null plist)
list
1 return
2 End if
Have reach end of list : print nodes
3 printReverse (plist->next)
4 Print (plist->data)
5 return
End printReverse
西南财经大学天府学院
10
Algorithm Analysis
• We answer the three question of “Limitation
of recursion”
1. Is the algorithm or data structure naturally suited to recursion?
Linear list is not a naturally recursive structure, and the algorithm
is not naturally suited to recursion.
2. Is the recursive solution shorter and more understandable?
Yes.
3. Does the recursive solution run in acceptable time and space
limits?
The number of linear list node can become quit large ,also the
algorithm has a linear efficiency (O(n)). ---- it is not a good for
recursion.
thus : It is not a good candidate for recursion
西南财经大学天府学院
11
6-4 Fibonacci number – another case study
Fibonacci number: Fibonacci number are a series in which
each number is sum of theProgram
previous
two numbers. The first few
Fibonacci
number in Fibonacci number
:
Thisare
program
prints out a Fibonacci series.
0, 1, 1, 2,
• Algorithm: print
1
2
3
4
Print (This program prints a fibonacci series.)
Print (How many number do you want? )
Read (seriesSize)
If (seriesSize < 2)
3, 5, 8,
13,
21, 34, ……
1
seriesSize = 2
5 end if
Fibonacci
number
6 Print (First
seriesSize Fibonacci number are: )
7 Looper = 0
8 Loop (looper < seriesSize )
1 nextFib = fib(looper)
2 print (nextFib )
3 looper = looper + 1
9 end loop
End Fibonacci
西南财经大学天府学院
12
Design algorithm of Fib(n):
base case: Fib(0) = 0 ,
n=0
Fib(4)
Fib(1) = 1 ,
n=1
Call
No
Call
general case : Fib
(n) = Fibfib(n(No
-val
1) num
+ Fib<integer>)
(n - 2)
Fib(3)
+
Fib(2)
Algorithm
1 number. 11
287
calculates the
• The generalization
of1nth Fibonacci
Fib(2)the +
Fib(1)the Fib(1)
+ Fib(0)
Pre num identified
Fibonacci
2
3 ordinal of 12
465 number
Fib(4)
Post
return the nth Fibonacci
number.
1
1
0
3OR num
13
753
1 If (num is 0
is5 1)
Fib(1)
+ Fib(0)
base case4 1
09
14
1219
• The algorithm
of
Fib(n)
2
1 return num
5
End if
15
15
1973
general case
6
25
16
21,891
Return (fib (num - 1) + fib (num - 2))
7
41
17
• Algorithm 3End
Analysis
fib
8
67
18
10
177
20
242,785
2,692,573
calulate Fibonacci numbers is not efficient for more than
9
109
19
29,860,703
20 numbers.
西南财经大学天府学院
13
331,160,281
6-5 The towers of hanoi
The towers of hanoi: monks had a set of three diamond
needle, stacked on the first needle were 64 gold disk of
decreasing size. The monks move one disk to another needle each
hour, subject to the following rules:
1. Only one disk could be moved at a time.
2. A large disk must never be stacked above a smaller one.
3. One and only one auxiliary needle could be used for
intermediate storage of disk.
The legend said that when all 64 disk had been transferred to
the destination needle,the world would end.
• The towers of hanoi with only three disk (start
position)
Source
auxiliary
西南财经大学天府学院
destination
14
Steps of generalize the problem:
case 1 : if we have only one disk to move
Move one disk from source to destination
case 2 : if we have two disk to move
Move one disk from source to auxiliary needle.
Move one disk from source to destination needle.
Move one disk from auxiliary to destination needle.
case 3 : if we have three disk to move
Move two disk from source to auxiliary needle.
Move one disk from source to destination needle.
Move two disk from auxiliary to destination needle.
generalization case : if we have n disk to move
Move n-1 disk from source to auxiliary needle.General case
Move one disk from source to destination needle.Base case
Move n-1 disk from auxiliary to destination needle.General case
15
西南财经大学天府学院
towers(3,A,C,B)
Algorithm towers ( val disks <integer>,
val source <character>,
towers(2,A,B,C)
step4
towers(2,B,C,A)
The algorithm of towers of hanoi:
val dest <character>,
val auxiliary <character>,
ref step <integer> )
towers
step2 tower
towers
step6
tower
recursively move
disk from
source to destination..
(1,A,C,B)
(1,C,B,A)
(1,B,A,C)
(1,A,C,B)
Pre the tower consists of integer disks
step1
step5
step7
source,step3
destination,
and auxiliary towers
given
Post
steps from moves printed
1 Print (“towers: ”, disks, source, dest, auxiliary )
2 If (disks = 1)
A
B “moveCfrom ”, source, “ to ”, dest)
1 print (“step
”, step,
2 step = step + 1
Start
3 Else
• Towers call for three
disks – 1, source, auxiliary, dest, step)
1 towers(disks
2 print (“step ”, step, “move from ”, source, “ to ”, dest)
C
A
B
A
B
C
3 C step = Astep + 1 B
4 towers(disks –step2
1, auxiliary, dest, source,
step)
step1
step3
4 End if
5 Return
End towers
A
B
C
16
西南财经大学天府学院
step4
Tracing of Algorithm towers
calls
output
tower (3,A,C,B)
tower (2,A,B,C)
tower (1,A,C,B)
step1: Move from A to C
step2: Move from A to B
tower (1,C,B,A)
step3: Move from C to B
step4: Move from A to C
tower (2,B,C,A)
tower (1,B,A,C)
step5: Move from B to A
step6: Move from B to C
tower (1,A,C,B)
step7:Move from A to C
西南财经大学天府学院
17
Summary of this chapter
There are two approaches to writing repetitive algorithms:
iteration and recursion.
1. Recursion is a repetitive process in which an algorithm calls
itself.
2. A repetitive algorithm uses recursion whenever the algorithm
appears within the definition itself.
When a program calls a subroutine, the current module suspends
processing and called subroutine takes over the control of the
program. When the subroutine completes its processing and
return to the module that called it, the module wakes up and
continue its processing.
When control is returned to a calling module, it must know four
pieces of information, which are stored in a stackframe:
a. The values of parameters
b. The values of local variables
c. Where it should return when its processing is down
d. The return value
西南财经大学天府学院
18
Summary of this chapter (Continue)
When a module calls a subroutine recursively, in each call, all of
the information needed by the subroutine is pushed in the
stackframe. The information is popped in the reverse order when
subroutines are terminated one after another, and finally the
control is returned to calling module.
A recursive algorithm has two elements: Each call either solves
only part of the problem or reduces the size of the problem.
The statement that solves the problem is known as the base case:
every recursive algorithm must have a base case.
The rest of the recursive algorithm is known as the general case.
The general rule for designing a recursive algorithm is as follows:
a. First, determine the base case.
b. Then, determine the general case.
c. combine the base case and the general case into an algorithm.
西南财经大学天府学院
19
Summary of this chapter (Continue)
You should not use recursion if the answer to any of the following
questions is no:
a. Is the algorithm or data structure naturally suited to recursion?
b. Is the recursive solution shorter and more understandable?
c. Does the recursive solution run in acceptable time and space
limits?
西南财经大学天府学院
20
Exercise
Consider the following algorithm
algorithm fun1(x <integer>)
1
if (x<5)
1 return (3*x)
2
else
1 return (2*fun1(x-5)+7)
3
end if
end fun1
What would be returned if fun1 is called as
fun1(4)
fun1(10)
fun1(12)
西南财经大学天府学院
21
Homework
设计一个递归算法求一个数组中的最大元素
设带头结点的线性链表中元素值为非零正整
数，试写出
求线性链表中所有元素之和的递归函数（
空表返回0)
求线性链表中所有元素最大值的递归函数
（空表返回0)
西南财经大学天府学院
22