遞歸匯總課件

第5章

遞歸

21世紀高等院校規(guī)劃教材返回總目錄5.1

?2006第5章

遞歸遞歸了解遞歸的定義遞歸的范例何時不要使用遞歸5.2

?2006遞歸了解遞歸的定義5.2關(guān)于遞歸遞歸：一個調(diào)用它本身的函數(shù)稱為遞歸（Recursive）。遞歸是一個比較抽象的問題，它隱含地利用了堆棧作為其存放臨時數(shù)據(jù)的場所，給人一種神秘的感覺。在程序設(shè)計中，利用遞歸來解決某些問題，既經(jīng)濟又方便。

5.3

?2006關(guān)于遞歸遞歸：一個調(diào)用它本身的函數(shù)稱為遞歸（Recursiv遞歸范例—計算某數(shù)的階乘計算某數(shù)的階乘。如求n!。n!=n*(n-1)!(n-1)!=(n-1)*(n-2)!(n-2)!=(n-2)*(n-3)!…1!=1

C語言程序段將以遞歸方式計算n!intfact(intn){intans;if(n==1)ans=1;elseans=n*fact(n-1);returnans;}

在編寫遞歸時必須有一個結(jié)束點，使得函數(shù)得以往上追溯。如上例中，當n=1時，1!=1即為其結(jié)束點。5.4

?2006遞歸范例—計算某數(shù)的階乘計算某數(shù)的階乘。C語言程序段將以遞歸遞歸范例—費波那契數(shù)列

費波那契數(shù)列（Fibonaccinumber）表示某一數(shù)為其前兩個數(shù)的和。假設(shè)n0=1,n1=1則n2=n1+n0=1+1=2n3=n2+n1=2+1=3…所以ni=ni-1+ni-2。

用C語言程序段將實現(xiàn)費波那契數(shù)列：intfibon(intn){intans;if(n==0||n==1)ans=1;elseans=fibon(n-1)+fibon(n-2);return(ans);}5.5

?2006遞歸范例—費波那契數(shù)列費波那契數(shù)列（Fibonaccin利用遞歸函數(shù)計算N階乘/*

filename:factor.c

Description:利用遞歸函數(shù)調(diào)用計算N階乘#include<stdio.h>#include<conio.h>#include<ctype.h>

/*函數(shù)原型聲明*/longFactorial(long);5.6

?2006利用遞歸函數(shù)計算N階乘/*5.6利用遞歸函數(shù)計算N階乘

（續(xù)1）voidmain(){

charch;

longn;printf("-----FactorialcountingUsingRecursive—--");

do

{printf("\nEnteranumber(0<=n<=12)tocountn!:");

scanf("%ld",&n);

/*n值在一般系統(tǒng)中超過13會產(chǎn)生overflow得到不正確的值*5.7

?2006利用遞歸函數(shù)計算N階乘

（續(xù)1）voidmain()5.利用遞歸函數(shù)計算N階乘

（續(xù)2）voidmain(){

charch;

longn;printf("-----FactorialcountingUsingRecursive—--");

do

{printf("\nEnteranumber(0<=n<=12)tocountn!:");

scanf("%ld",&n);

/*n值在一般系統(tǒng)中超過13會產(chǎn)生overflow得到不正確的值*5.8

?2006利用遞歸函數(shù)計算N階乘

（續(xù)2）voidmain()5.利用遞歸函數(shù)計算N階乘

（續(xù)3）if(n<0||n>12)

printf("inputoutofrange!\n");

else

printf("%ld!=%ld\n",n,Factorial(n));

printf("Continue(y/n)?");

ch=toupper(getche());

}while(ch=='Y');}5.9

?2006利用遞歸函數(shù)計算N階乘

（續(xù)3）if(n利用遞歸函數(shù)計算N階乘

（續(xù)4）/*利用遞歸調(diào)用自己計算N階乘*/longFactorial(longn){

if(n==1||n==0)

return(1);

else

return(n*Factorial(n-1));}5.10

?2006利用遞歸函數(shù)計算N階乘

（續(xù)4）/*利用遞歸調(diào)用自己計算N程序?qū)嵗妮敵鼋Y(jié)果-----FactorialcountingUsingRecursive----Enteranumber(0<=n<=12)tocountn!:55!=120Continue(y/n)?n5.11

?2006程序?qū)嵗妮敵鼋Y(jié)果-----Factorialcounti程序?qū)嵗某绦蛘f明例如，n=5時，遞歸函數(shù)執(zhí)行如下：Factorial(5)=5*Factorial(4) =5*(4*Factorial(3)) =5*(4*(3*Factorial(2))) =5*(4*(3*(2*Factorial(1)))) =5*(4*(3*(2*1))) =5*(4*(3*2)) =5*(4*6) =5*24 =1205.12

?2006程序?qū)嵗某绦蛘f明例如，n=5時，遞歸函數(shù)執(zhí)行如下：5.12利用循環(huán)做N階乘的計算/*

filename:factor_i.c Description:Factorialnumberscountunsingiterative

利用循環(huán)做N階乘的計算*/#include<stdio.h>#include<conio.h>#include<ctype.h>/*函數(shù)原型聲明*/longFactorial(long);5.13

?2006利用循環(huán)做N階乘的計算/*5.13利用循環(huán)做N階乘的計算（續(xù)1）voidmain(){ charch; longn;printf("-----FactorialcountingusingIterative-----");do { printf("\nEnteranumber(0<=n<=12)tocountn!:"); scanf("%ld",&n);5.14

?2006利用循環(huán)做N階乘的計算（續(xù)1）voidmain()5.1利用循環(huán)做N階乘的計算（續(xù)2）if(n<0||n>12) printf("Inputoutofrange!\n"); else printf("%ld!=%ld\n",n,Factorial(n));

printf("Continue(y/n)?"); ch=toupper(getche()); }while(ch=='Y');}

longFactorial(longn){ longsum=1; inti;5.15

?2006利用循環(huán)做N階乘的計算（續(xù)2）if利用循環(huán)做N階乘的計算（續(xù)3）if(n==0||n==1)/*當n=0或n=1時，0!=1，1!=1*/

return(1);/*直接傳回1*/

else { for(i=2;i<=n;i++)/*sum記錄目前階乘之和*/

sum*=i;/*sum與i相乘之和放回sum中*/ }

return(sum);}5.16

?2006利用循環(huán)做N階乘的計算（續(xù)3）if(n==程序?qū)嵗妮敵鼋Y(jié)果-----FactorialcountingusingIterative-----Enteranumber(0<=n<=12)tocountn!:1010!=3628800Continue(y/n)?n5.17

?2006程序?qū)嵗妮敵鼋Y(jié)果-----Factorialcount利用函數(shù)遞歸調(diào)用做費波那契數(shù)列計算/*

filename:fib.c Description:Fibonaccinumbers

利用函數(shù)遞歸調(diào)用做費氏數(shù)列計算費氏數(shù)列為0,1,1,2,3,5,8,12,21,…其中某一項為前兩項之和，且第0項為0，第1項為1*/#include<stdio.h>#include<conio.h>#include<ctype.h>5.18

?2006利用函數(shù)遞歸調(diào)用做費波那契數(shù)列計算/*5.18利用函數(shù)遞歸調(diào)用做費波那契數(shù)列計算（續(xù)1）/*函數(shù)原型聲明*/longFibonacci(long);voidmain(){ charch; longn;printf("-----FibonaciinumbersUsingRecursive-----"); do {5.19

?2006利用函數(shù)遞歸調(diào)用做費波那契數(shù)列計算（續(xù)1）/*函數(shù)原型聲利用函數(shù)遞歸調(diào)用做費波那契數(shù)列計算（續(xù)2）

printf("\nEnteranumber(n>=0):"); scanf("%ld",&n); /*n值大于0*/

if(n<0) printf("Numbermustbe>0\n"); else printf("Fibonacci(%ld)%ld\n",n,Fibonacci(n)); printf("Contiune(y/n)?"); ch=toupper(getche()); }while(ch=='Y');}5.20

?2006利用函數(shù)遞歸調(diào)用做費波那契數(shù)列計算（續(xù)2） pr利用函數(shù)遞歸調(diào)用做費波那契數(shù)列計算（續(xù)3）/*利用遞歸函數(shù)調(diào)用本身函數(shù)來計算Fibonaccinumbers*/longFibonacci(longn){ if(n==0)/*第0項為0*/

return(0); elseif(n==1)/*第1項為1*/

return(1); else/*遞歸調(diào)用函數(shù)第N項為n-1跟

n-2項之和*/

return(Fibonacci(n-1)+Fibonacci(n-2));}5.21

?2006利用函數(shù)遞歸調(diào)用做費波那契數(shù)列計算（續(xù)3）/*利用遞歸函程序?qū)嵗妮敵鼋Y(jié)果----FibonaciinumbersUsingRecursive-----Enteranumber(n>=0):15Fibonacci(15)=987Continue(y/n)?yEnteranumber(n>=0):25Fibonacci(25)=121393Continue(y/n)?n程序說明：費氏數(shù)列為1,1,2,3,5,8,13,21,…，其中某一項為前兩項之和，且第0項為0，第1項為1。5.22

?2006程序?qū)嵗妮敵鼋Y(jié)果----Fibonaciinumbers利用循環(huán)法計算費氏數(shù)列/*

filename:fib_i.c Description:Fibonaccinumberscountusingiterative

利用循環(huán)法計算費氏數(shù)列費氏數(shù)列為0,1,1,2,3,5,8,13,21,…

其中某一項為前兩項之和，且第0項為0，第1項為1*/5.23

?2006利用循環(huán)法計算費氏數(shù)列/*5.23利用循環(huán)法計算費氏數(shù)列

（續(xù)1）#include<stdio.h>#include<conio.h>#include<ctype.h>/*函數(shù)原型聲明*/longFibonacci(long);voidmain(){ charch; longn;5.24

?2006利用循環(huán)法計算費氏數(shù)列

（續(xù)1）#include<std利用循環(huán)法計算費氏數(shù)列

（續(xù)2）printf("-----FibonaccinumbersUsingIterative-----"); do { printf("\nEnteranumber(n>=0):"); scanf("%ld",&n); /*n值大于0*/

if(n<0) printf("Inputnumbermustbe>0!\n"); else printf("Fibonacci(%ld)=%ld\n",n,Fibonacci(n));5.25

?2006利用循環(huán)法計算費氏數(shù)列

（續(xù)2）printf("利用循環(huán)法計算費氏數(shù)列

（續(xù)3）printf("Continue(y/n)?"); ch=toupper(getche()); }while(ch=='Y');}longFibonacci(longn){

longbackitem1;/*前一項值*/longbackitem2;/*前兩項值*/

longthisitem;/*目前項數(shù)值*/

longi;5.26

?2006利用循環(huán)法計算費氏數(shù)列

（續(xù)3）pri利用循環(huán)法計算費氏數(shù)列

（續(xù)4）if(n==0)/*費氏數(shù)列第0項為0*/

return(0); elseif(n==1)/*第2項為1*/

return(1); else { backitem2=0; backitem1=1; /*利用循環(huán)將前兩項相加后放入目前項*/ /*之后改變前兩項的值直到第n項求得*/5.27

?2006利用循環(huán)法計算費氏數(shù)列

（續(xù)4）if(n=利用循環(huán)法計算費氏數(shù)列

（續(xù)5）for(i=2;i<=n;i++) { /*F(i)=F(i-1)+F(i-2)*/ thisitem=backitem1+backitem2; /*改變前兩項之值*/

backitem2=backitem1; backitem1=thisitem; }

return(thisitem); }}5.28

?2006利用循環(huán)法計算費氏數(shù)列

（續(xù)5）fo程序段輸出結(jié)果-----FibonaccinumbersUsingIterative-----Enteranumber(n>=0):10Fibonacci(10)=89Continue(y/n)?yEnteranumber(n>=0):20Fibonacci(20)=10946Continue(y/n)?n5.29

?2006程序段輸出結(jié)果-----Fibonaccinumbers何時不要使用遞歸遞歸雖然可以使用少數(shù)幾行的敘述就可解決一個復(fù)雜的問題，但有些問題會導(dǎo)致花更多的時間。由于非遞歸使用了較多的區(qū)域變量（localvariable），所以直覺上以為遞歸會較好，其實不然，因為遞歸使用了更多的時間存