遞歸函數(shù)車萬翔哈爾濱工業(yè)大學(xué)遞歸函數(shù)車萬翔1兩個(gè)和尚的故事“從前有座山,山里有座廟,廟里有個(gè)老和尚給小和尚講故事,講什么呢?” “從前有座山,山里有座廟,廟里有個(gè)老和尚給小和尚講故事,講什么呢?”“從前有座山,山里有座廟,廟里有個(gè)老和尚給小和尚講故事,講什么呢?”………兩個(gè)和尚的故事“從前有座山,山里有座廟,廟里有個(gè)老和尚給小和2遞歸的定義遞歸：程序調(diào)用自身形式：在函數(shù)定義有直接或間接調(diào)用自身遞歸的定義形式：在函數(shù)定義有直接或間接調(diào)用自身3階乘階乘：def

p(n):x=

1i=

1whilei<=

n:x=x*

ii=i+

1return

xn

=

int(raw_input("請(qǐng)輸入一個(gè)整數(shù):"))print

n,"!的值為",p(n)階乘階乘：4階乘階乘：p(n)?!=(???)!×?p(n-1)p(n-1)(???)!=(???)!×(???)p(n-2)階乘階乘：5階乘階乘：else:def

p(n):ifn==1orn==

0:return

1returnn*

p(n-1)n

=

int(raw_input("請(qǐng)輸入一個(gè)整數(shù):"))print

n,"

!的值為：",p(n)階乘階乘：else:defp(n):6階乘p(3)def

p(3):if3==1or

3==0:return

1else:return3*

p(3-1)def

p(2):if2==1or2==

0:return

1else:return2*

p(2-1)1defifp(1):1==1or

1==0:return

1else:return1*

p(1-1)26階乘p(3)defp(3):defp(2):else:27遞歸初始條件階乘def

p(n):ifn==1orn==

0:return

1else:returnn*

p(n-1)掐頭去尾留中間遞歸初始條件階乘defp(n):ifn==1or8遞歸解決問題的思想if

問題足夠簡單:直接解決問題返回解else:將問題分解為與原問題同構(gòu)的一個(gè)或多個(gè)更小的問題逐個(gè)解決這些更小的問題將結(jié)果組合為，獲得最終的解返回解遞歸解決問題的思想if問題足夠簡單:9兔子數(shù)列第一個(gè)月第二個(gè)月第三個(gè)月第四個(gè)月第五個(gè)月第六個(gè)月兔子數(shù)列第一個(gè)月10兔子數(shù)列斐波那契數(shù)列是這樣一個(gè)數(shù)列：1,

1,

2,

3,5,

8,13,

21,34,

55,

89……兔子數(shù)列斐波那契數(shù)列11def

fib(n):ifn==1orn==

2:return1 初始條件遞歸 else:returnfib(n-1)+

fib(n-2)斐波那契數(shù)列斐波那契數(shù)列：1,

1,

2,

3,

5,

8,

13,

21……ifn==1orn==2:遞歸 else:斐波12斐波那契數(shù)列def

fib(4):if4==1or4==

2:return

1else:returnfib(4-1)+

fib(4-2)fib(4)def

fib(3):if3==1or3==

2:return

1else:returnfib(3-1)+

fib(3-2)def

fib(1):if1==1or1==

2:return

1else:returnfib(1-1)+

fib(1-2)def

fib(2):if2==1or2==

2:return

1else:returnfib(2-1)+

fib(2-2)斐波那契數(shù)列deffib(4):fib(4)deffib13遞歸

-

漢諾塔在印度，有這么一個(gè)古老的傳說:開天辟地的神勃拉瑪（和中國的盤古差不多的神）在一個(gè)廟里留下了三根金剛石的棒，第一根上面套著64個(gè)圓的金片，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去，廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不能放在小的上面移動(dòng)圓片的次數(shù):18446744073709551615遞歸-漢諾塔在印度，有這么一個(gè)古老的傳說:移動(dòng)圓片的次數(shù)14高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件15高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件16高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件17高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件18高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件19高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件20高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件21高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件22高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件23高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件24高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件25高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件26高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件27高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件28高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件29高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件30高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件31高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件32高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件33高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件34高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件35高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件36高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件37高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件38高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件39高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件40高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件41高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件42高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件43高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件44高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件45高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件46高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件47高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件48高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件49高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件50遞歸解決方案將前

n-1

個(gè)盤子，通過

C，從

A

移動(dòng)到

B從

A

到

C移動(dòng)第

n

個(gè)盤子將前

n-1

個(gè)盤子，通過

A，從

B

移動(dòng)到

C遞歸解決方案將前n-1個(gè)盤子，通過C，從A移動(dòng)到51遞歸

-

漢諾塔定義函數(shù)hanoi(n,

A,

B,

C)表示把A上的n個(gè)盤子移動(dòng)到C上，其中可以用到Bdefhanoi(n,A,B,

C):ifn==

1:print"Movedisk",n,"from",A,"to",Celse:hanoi(n-1,A,C,B)print"Movedisk",n,"from",A,"to",Chanoi(n-1,B,A,C)n

=

int(raw_input("請(qǐng)輸入一個(gè)整數(shù):

"))hanoi(n,

'左','中','右')遞歸-漢諾塔定義函數(shù)hanoi(n,A,B,C)表52路邊停車路邊停車53隨機(jī)停車長度為5的馬路，平均能停多少量長度為1的汽車？隨機(jī)停車長度為5的馬路，平均能停多少量長度為1的汽車？54隨機(jī)停車長度為5的馬路，平均能停多少量長度為1的汽車？隨機(jī)停車長度為5的馬路，平均能停多少量長度為1的汽車？55隨機(jī)停車隨機(jī)停車56隨機(jī)停車隨機(jī)停車57隨機(jī)停車隨機(jī)停車58隨機(jī)停車當(dāng)寬度w足夠大時(shí)，平均停車約

0.7475972w輛常數(shù)

0.7475972

被稱作Renyi

停車常數(shù)該算法巧妙的運(yùn)用了遞歸思想，將大問題分解為更小的、獨(dú)立的相似問題，然后分別加以解決許多問題能夠以此方式解決隨機(jī)停車當(dāng)寬度w足夠大時(shí)，平均停車約0.7475972w59遞歸的時(shí)間開銷def

fib_loop(n):ifn==1orn==2:return

1else:i=

2f1=

1f2=

1while(i<

n):f3=f1+

f2f1=

f2f2=

f3i=i+

1return

f3def

fib_recursive(n):ifn==1orn==

2:return1else:returnfib_recursive(n-1)+

fib_recursive(n-2)fib_loop(100)fib_recursive(100)不到0.01秒超過1小時(shí)時(shí)間都去哪了？遞歸的時(shí)間開銷deffib_loop(n):deffib60遞歸的時(shí)間開銷def

fib(4):if4==1or4==

2:return

1else:returnfib(4-1)+

fib(4-2)fib(4)def

fib(3):if3==1or3==

2:return

1else:returnfib(3-1)+

fib(3-2)def

fib(1):if1==1or1==

2:return

1else:returnfib(1-1)+

fib(1-2)def

fib(2):if2==1or2==

2:return

1else:returnfib(2-1)+

fib(2-2)遞歸的時(shí)間開銷deffib(4):fib(4)deffi61遞歸的優(yōu)劣分析優(yōu)勢（strength）它能使一個(gè)蘊(yùn)含遞歸關(guān)系且結(jié)構(gòu)復(fù)雜的程序簡潔精煉，增加可讀性特別是在難于找到從邊界到解的全過程的情況下，如果把問題推進(jìn)一步,其結(jié)果仍維持原問題的關(guān)系劣勢（weakness）嵌套層次深，函數(shù)調(diào)用開銷大重復(fù)計(jì)算遞歸的優(yōu)劣分析優(yōu)勢（strength）62遞歸函數(shù)車萬翔哈爾濱工業(yè)大學(xué)遞歸函數(shù)車萬翔63兩個(gè)和尚的故事“從前有座山,山里有座廟,廟里有個(gè)老和尚給小和尚講故事,講什么呢?” “從前有座山,山里有座廟,廟里有個(gè)老和尚給小和尚講故事,講什么呢?”“從前有座山,山里有座廟,廟里有個(gè)老和尚給小和尚講故事,講什么呢?”………兩個(gè)和尚的故事“從前有座山,山里有座廟,廟里有個(gè)老和尚給小和64遞歸的定義遞歸：程序調(diào)用自身形式：在函數(shù)定義有直接或間接調(diào)用自身遞歸的定義形式：在函數(shù)定義有直接或間接調(diào)用自身65階乘階乘：def

p(n):x=

1i=

1whilei<=

n:x=x*

ii=i+

1return

xn

=

int(raw_input("請(qǐng)輸入一個(gè)整數(shù):"))print

n,"!的值為",p(n)階乘階乘：66階乘階乘：p(n)?!=(???)!×?p(n-1)p(n-1)(???)!=(???)!×(???)p(n-2)階乘階乘：67階乘階乘：else:def

p(n):ifn==1orn==

0:return

1returnn*

p(n-1)n

=

int(raw_input("請(qǐng)輸入一個(gè)整數(shù):"))print

n,"

!的值為：",p(n)階乘階乘：else:defp(n):68階乘p(3)def

p(3):if3==1or

3==0:return

1else:return3*

p(3-1)def

p(2):if2==1or2==

0:return

1else:return2*

p(2-1)1defifp(1):1==1or

1==0:return

1else:return1*

p(1-1)26階乘p(3)defp(3):defp(2):else:269遞歸初始條件階乘def

p(n):ifn==1orn==

0:return

1else:returnn*

p(n-1)掐頭去尾留中間遞歸初始條件階乘defp(n):ifn==1or70遞歸解決問題的思想if

問題足夠簡單:直接解決問題返回解else:將問題分解為與原問題同構(gòu)的一個(gè)或多個(gè)更小的問題逐個(gè)解決這些更小的問題將結(jié)果組合為，獲得最終的解返回解遞歸解決問題的思想if問題足夠簡單:71兔子數(shù)列第一個(gè)月第二個(gè)月第三個(gè)月第四個(gè)月第五個(gè)月第六個(gè)月兔子數(shù)列第一個(gè)月72兔子數(shù)列斐波那契數(shù)列是這樣一個(gè)數(shù)列：1,

1,

2,

3,5,

8,13,

21,34,

55,

89……兔子數(shù)列斐波那契數(shù)列73def

fib(n):ifn==1orn==

2:return1 初始條件遞歸 else:returnfib(n-1)+

fib(n-2)斐波那契數(shù)列斐波那契數(shù)列：1,

1,

2,

3,

5,

8,

13,

21……ifn==1orn==2:遞歸 else:斐波74斐波那契數(shù)列def

fib(4):if4==1or4==

2:return

1else:returnfib(4-1)+

fib(4-2)fib(4)def

fib(3):if3==1or3==

2:return

1else:returnfib(3-1)+

fib(3-2)def

fib(1):if1==1or1==

2:return

1else:returnfib(1-1)+

fib(1-2)def

fib(2):if2==1or2==

2:return

1else:returnfib(2-1)+

fib(2-2)斐波那契數(shù)列deffib(4):fib(4)deffib75遞歸

-

漢諾塔在印度，有這么一個(gè)古老的傳說:開天辟地的神勃拉瑪（和中國的盤古差不多的神）在一個(gè)廟里留下了三根金剛石的棒，第一根上面套著64個(gè)圓的金片，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去，廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不能放在小的上面移動(dòng)圓片的次數(shù):18446744073709551615遞歸-漢諾塔在印度，有這么一個(gè)古老的傳說:移動(dòng)圓片的次數(shù)76高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件77高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件78高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件79高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件80高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件81高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件82高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件83高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件84高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件85高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件86高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件87高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件88高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件89高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件90高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件91高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件92高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件93高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件94高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件95高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件96高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件97高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件98高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件99高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件100高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件101高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件102高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件103高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件104高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件105高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件106高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件107高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件108高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件109高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件110高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件111高級(jí)語言程序設(shè)計(jì)(Python)07-教學(xué)課件_9課件112遞歸解決方案將前

n-1

個(gè)盤子，通過

C，從

A

移動(dòng)到

B從

A

到

C移動(dòng)第

n

個(gè)盤子將前

n-1

個(gè)盤子，通過

A，從

B

移動(dòng)到

C遞歸解決方案將前n-1個(gè)盤子，通過C，從A移動(dòng)到113遞歸

-

漢諾塔定義函數(shù)hanoi(n,

A,

B,

C)表示把A上的n個(gè)盤子移動(dòng)到C上，其中可以用到Bdefhanoi(n,A,B,

C):ifn==

1:print"Movedisk",n,"from",A,"to",Celse:hanoi(n-1,A,C,B)print"Movedisk",n,"from",A,"to",Chanoi(n-1,B,A,C)n

=

int(raw_input("請(qǐng)輸入一個(gè)整數(shù):

"))hanoi(n,

'左','中','右')遞歸-漢諾塔定義函數(shù)hanoi(n,A,B,C)表114路邊停車路邊停車115隨機(jī)停車長度為5的馬路，平均能停多少量長度為1的汽車？隨機(jī)停車長度為5的馬路，平均能停多少量長度為1的汽車？116隨機(jī)停車長度為5的馬路，平均能停多少量長度為1的汽車？隨機(jī)停車長度為5的馬路，平均能停多少量長度為1的汽車？117隨機(jī)停車隨機(jī)停車118隨機(jī)停車隨機(jī)停車119隨機(jī)停車隨機(jī)停車120隨機(jī)停車當(dāng)寬度w足夠大時(shí)，平均停車約

0.7475972w輛常數(shù)

0.7475972

被稱作Renyi

停車常數(shù)該算法巧妙的運(yùn)用了遞歸思想，將大問題分