2014級(jí)程序設(shè)計(jì)語言課件遞歸

遞歸問題的提出“漢諾塔”（Hanoi）–這是一個(gè)必須用遞歸方法才能解決的問題–n=64時(shí)，18,446,744,073,709,551,615次–1844億億次–每次1微秒，需要60萬年遞歸問題的提出A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn=3遞歸問題的提出A→C，A→B，C→B，A→C，B→A，B→C，A→CABC遞歸問題的提出A→C，A→B，C→B，A→C，B→A，B→C，A→CABC遞歸問題的提出A→C，A→B，C→B，A→C，B→A，B→C，A→CABC遞歸問題的提出A→C，A→B，C→B，A→C，B→A，B→C，A→CABCn更大些怎么辦？遞歸問題的提出第一步：將問題簡化。–假設(shè)A桿上只有2個(gè)圓盤，即漢諾塔有2層，n＝2。A

B

C遞歸問題的提出對(duì)于一個(gè)有n（n>1）個(gè)圓盤的漢諾塔，將n個(gè)圓盤分為兩部分：上面的n-1

個(gè)圓盤和最下面的n號(hào)圓盤。將

“上面的n-1個(gè)圓盤”看成一個(gè)整體。將n-1個(gè)盤子從一根木樁移到另一根木樁上將1個(gè)盤子從一根木樁移到另一根木樁上A

B

C9解決漢諾塔問題的算法(C)void

Hanoi

(int

n,

char

A,

char

B,

char

C

){if

(n==

1

)move(1,A,

C);else{Hanoi

(n-1,

A,C,

B

);move(n,A,

C);Hanoi

(n-1,

B,

A,

C);}}例求整數(shù)n的階乘n！計(jì)算n！=n

*(n-1)*(n-2)*…*1迭代法用遞歸的方法例求整數(shù)n的階乘n！#include

<stdio.h>main(){int n,

i;long

result=1;printf("Input

n:");scanf("%d",

&n);for

(i=1;

i<=n;

i++)result

*=

i;printf("%d!=

%ld",

n,

result);}迭代法long

fact(long

n){long

result;if

(n

<0)return

–1;elseif

(n==0||

n==1)

/*遞歸終止條件*/return

1;elsereturn(n

*

fact(n-1));/*遞歸調(diào)用*/}例求整數(shù)n的階乘n！遞歸法#include

<stdio.h>long

fact(long

n);main(){int

n;long

result;printf("Input

n:

");scanf("%d",

&n);result

=

fact(n);if(result==-1)printf("n<0,data

error

!

\

n");elseprintf("%d!

=

%ld\n",

n,

result);}例求整數(shù)n的階乘n！遞歸法14計(jì)算fact(4)計(jì)算

4*fact(3)計(jì)算

3*fact(2)計(jì)算

2*fact(1)計(jì)算

fact(1)遞歸調(diào)用回歸求值返回24返回6返回2返回1求解階乘n!的過程遞歸函數(shù)遞歸方法的基本原理將復(fù)雜問題逐步化簡，最終轉(zhuǎn)化為一個(gè)最簡單的問題最簡單問題的解決，就意味著整個(gè)問題的解決遞歸調(diào)用應(yīng)該能夠在有限次數(shù)內(nèi)終止遞歸遞歸調(diào)用如果不加以限制，將無數(shù)次的循環(huán)調(diào)用必須在函數(shù)內(nèi)部加控制語句，只有當(dāng)滿足一定條件時(shí)，遞歸終止有時(shí)將其稱為條件遞歸遞歸函數(shù)任何一個(gè)遞歸調(diào)用程序必須包括兩部分遞歸循環(huán)繼續(xù)的過程遞歸調(diào)用結(jié)束的過程if(遞歸終止條件成立)遞歸公式的初值;returnelsereturn遞歸函數(shù)調(diào)用返回的結(jié)果值;遞歸函數(shù)思考：下面程序有什么問題階乘函數(shù)的遞歸實(shí)現(xiàn)unsigned

long

Fac(unsignedint

n){if

(n

<

0)printf("data

error!");else

if

(n==0

||

n==1)return

1;elsereturn

n

*

Fac(n-1);}編譯這個(gè)程序也會(huì)給出警告，提示“非所有控制分支都有返回值”。同時(shí)，運(yùn)行程序后如果我們輸入了一個(gè)負(fù)數(shù)，那么程序運(yùn)行結(jié)果為：

Inputa:-1↙Input

data

error!a!

=

11如果某個(gè)函數(shù)需要返回值的話，那么一定要確保該函數(shù)中的所有