4.5遞歸算法與遞歸程序

4.5遞歸算法與遞歸程序授課教師：周杰學(xué)習(xí)目標(biāo)了解遞歸算法的基本概念及執(zhí)行過(guò)程能認(rèn)識(shí)用遞歸解決問(wèn)題的方法遞歸算法與遞歸程序活動(dòng)一:《猴子吃桃》問(wèn)題求解有一天小猴子摘了若干個(gè)桃子，當(dāng)即吃了一半還覺(jué)得不過(guò)癮，又多吃了一個(gè)。第二天接著吃剩下桃子中的一半，仍覺(jué)得不過(guò)癮又多吃了一個(gè)。以后小猴子都是吃尚存桃子的一半多一個(gè)。到第10天早上小猴子再去吃桃子的時(shí)候，看到只剩下一個(gè)桃子。問(wèn)小猴子在第7天時(shí)還剩下多少個(gè)桃子?在第

1天時(shí)共摘下了多少個(gè)桃子?

活動(dòng)一:《猴子吃桃》算法分析分析

tao(8)=——

(tao(10)+1)*2tao(9)=

tao(10)=10設(shè)天數(shù)為n

桃子數(shù)為tao

14——

(tao(9)+1)*2…

tao(n)=?——

(tao(?)+1)*2tao=?n=10tao(n)=(tao(?)+1)*2

n<101

數(shù)學(xué)遞推公式活動(dòng)一:《猴子吃桃》算法分析數(shù)學(xué)遞推公式tao(n)=?n=10tao(n)=(tao(?)+1)*2

n<101

n+1如果否則tao=(?+1)*2

Functiontao(n)

EndFunctionn=10，則tao=?

遞歸調(diào)用B.順序執(zhí)行A.自己調(diào)用自己函數(shù)遞歸調(diào)用Function如果n=10，則tao=1否則tao=(+1)*2

EndFunctiontao(n)tao(n+1)思考：遞歸算法描述的特點(diǎn)是什么？遞歸算法的概念Function

tao(n)AsInteger

ifn=10thentao=1Elsetao=(tao(n+1)+1)*2EndifEndFunction遞歸算法執(zhí)行過(guò)程Functiontao(n

)AsIntegerIfn=10thentao=1Elsetao=(tao(n+1)+1)*2n=1tao(1)=?tao(1)=(tao(2)+1)*2Functiontao(2

)AsIntegerIfn=10thentao=1Elsetao=(tao(n+1)+1)*2n=2tao(2)=?tao(2)=(tao(3)+1)*2n=3tao(3)=?Functiontao(3

)AsIntegerIfn=10thentao=1Elsetao=(tao(n+1)+1)*2……Functiontao(10

)AsIntegerIfn=10thentao=1Elsetao=(tao(n+1)+1)*2n=10tao(10)=1……tao(3)=(tao(4)+1)*2???tao(4)=190tao(9)=4tao(3)=382tao(2)=766tao(1)=1534……Functiontao(n)

ifn=10thentao=1Elsetao=(tao(n+1)+1)*2EndifEndFunction

遞歸算法:在程序的函數(shù)定義中直接使用或者間接使用的自己調(diào)用自己的編程方法。思考：遞歸算法的描述特點(diǎn)是什么？函數(shù)名函數(shù)名遞歸算法的概念B.順序執(zhí)行A.自己調(diào)用自己函數(shù)遞歸調(diào)用Functiontao(n)

ifn=10thentao=1Elsetao=(tao(n+1)+1)*2EndifEndFunction遞歸算法的概念函數(shù)遞歸調(diào)用活動(dòng)二：計(jì)算機(jī)怎樣執(zhí)行遞歸程序？遞推回歸遞歸tao(1)=tao(2)=tao(3)=tao(9)=tao(10)=1……tao(9)=4tao(3)=382tao(2)=766tao(1)=1534……活動(dòng)二：想一想，議一議輸入的第一組數(shù)據(jù)（3，10）求的是什么?問(wèn)題2第3天的桃子數(shù),382個(gè)。遞推與回歸的轉(zhuǎn)折點(diǎn)是n=10，tao(10)=1。問(wèn)題1問(wèn)題3輸入第三組數(shù)據(jù)，程序運(yùn)行出現(xiàn)什么結(jié)果？請(qǐng)分析原因。報(bào)溢出錯(cuò)誤。問(wèn)題3問(wèn)題1問(wèn)題2輸入（1，0）程序不能停止調(diào)用遞歸程序必須要有結(jié)束遞歸調(diào)用的條件活動(dòng)二：想一想，議一議其中“遞推過(guò)程”有何特點(diǎn)？C.沒(méi)完沒(méi)了A.小題大做B.大事化了問(wèn)題2按同一函數(shù)模型轉(zhuǎn)化問(wèn)題到更接近于結(jié)束遞歸的條件。問(wèn)題3問(wèn)題1必須要有結(jié)束遞歸調(diào)用的條件活動(dòng)二：想一想，議一議按同一模型轉(zhuǎn)化問(wèn)題到更接近于結(jié)束遞歸調(diào)用的條件。問(wèn)題1問(wèn)題2問(wèn)題3用遞歸法解決問(wèn)題的兩個(gè)條件

必須要有結(jié)束遞歸調(diào)用的條件。Functiontao(n)如果

n=1