3.2.4遞歸函數(shù)程序設(shè)計(jì) - 遞歸函數(shù)程序設(shè)計(jì)

第三章函數(shù)程序設(shè)計(jì)第2節(jié)遞歸函數(shù)程序設(shè)計(jì)

1程序解析2遞歸函數(shù)基本概念3遞歸程序設(shè)計(jì)1漢諾(Hanoi)塔問題解析

將64個(gè)盤從座A搬到座B(1)一次只能搬一個(gè)盤子(2)盤子只能插在A、B、C三個(gè)桿中(3)大盤不能壓在小盤上

A B C分析

A B C分析

A B C

A B Cnn-1n-1分析

A B C

A B Cn1漢諾(Hanoi)塔問題解析遞歸方法的兩個(gè)要點(diǎn)（1）遞歸出口：一個(gè)盤子的解決方法；（2）遞歸式子：如何把搬動64個(gè)盤子的問題簡化成搬動63個(gè)盤子的問題。把漢諾塔的遞歸解法歸納成三個(gè)步驟：n-1個(gè)盤子從座A搬到座C第n號盤子從座A搬到座Bn-1個(gè)盤子從座C搬到座B算法：hanio(n個(gè)盤，A→B，C為過渡){if(n==1)

直接把盤子A→Belse{hanio(n-1個(gè)盤，A→C，B為過渡)

把第n號盤A→B hanio(n-1個(gè)盤，C→B，A為過渡) }}

A B Cn-12遞歸函數(shù)基本概念例

用遞歸函數(shù)實(shí)現(xiàn)求n！遞推法在學(xué)習(xí)循環(huán)時(shí)，計(jì)算n！采用的就是遞推法：

n！=1×2×3×…×n用循環(huán)語句實(shí)現(xiàn)：

result=1; for(i=1;i<=n;i++) result=result*i;遞歸法n！=n×(n-1)! 當(dāng)n＞1 遞歸式子=1 當(dāng)n=1或n=0 遞歸出口即求n！可以在(n-1)！的基礎(chǔ)上再乘上n。如果把求n！寫成函數(shù)fact(n)，則fact(n)的實(shí)現(xiàn)依賴于fact(n-1)。例10-2用遞歸函數(shù)求n!。#include<stdio.h>doublefact(intn)；intmain(void){intn;scanf("%d",&n);printf("%f",fact(n));return0;}doublefact(intn) /*函數(shù)定義*/{doubleresult;

if(n==1||n==0) /*遞歸出口*/result=1;elseresult=n*fact(n-1);

returnresult;}2遞歸函數(shù)基本概念遞歸式遞歸出口分析求n!遞歸定義n!=n*(n-1)!(n>1)n!=1(n=0,1)#include<stdio.h>doublefact(intn)；intmain(void){intn;scanf("%d",&n);printf("%f",fact(n));return0;}doublefact(intn){doubleresult;

if(n==1||n==0)result=1;elseresult=n*fact(n-1);

returnresult;}fact(n)=n*fact(n-1);main()fact(3)fact(2)fact(1){....{....{....{....printf(fact(3))f=3*fact(2)f=2*fact(1)f=1}return(f)return(f)return(f)}}}遞歸函數(shù)fact(n)的實(shí)現(xiàn)過程fact(3)=3*fact(2)＝

2*fact(1)＝

fact(1)＝12*1=23*2=6同時(shí)有4個(gè)函數(shù)在運(yùn)行，且都未完成3遞歸程序設(shè)計(jì)用遞歸實(shí)現(xiàn)的問題，滿足兩個(gè)條件：問題可以逐步簡化成自身較簡單的形式（遞歸式）n!=n*(n-1)!nn-1Σi=n+Σi

i=1i=1遞歸最終能結(jié)束(遞歸出口)兩個(gè)條件缺一不可解決遞歸問題的兩個(gè)著眼點(diǎn)3遞歸程序設(shè)計(jì)例

編寫遞歸函數(shù)reverse(intn)實(shí)現(xiàn)將整數(shù)n逆序輸出。

分析：將整數(shù)n逆序輸出可以用循環(huán)實(shí)現(xiàn)，且循環(huán)次數(shù)與n的位數(shù)有關(guān)。遞歸實(shí)現(xiàn)整數(shù)逆序輸出也需要用位數(shù)作為控制點(diǎn)。歸納遞歸實(shí)現(xiàn)的兩個(gè)關(guān)鍵點(diǎn)如下：遞歸出口：直接輸出n，如果n<=9，即n為1位數(shù)遞歸式子：輸出個(gè)位數(shù)n%10，再遞歸調(diào)用reverse(n/10)輸出前n-1位，如果n為多位數(shù)3遞歸程序設(shè)計(jì)由于結(jié)果是在屏幕上輸出，因此函數(shù)返回類型為voidvoidreverse(intnum){ if(num<=9) printf("%d",num); /*遞歸出口*/ else{ printf("%d",num%10); reverse(num/10); /*遞歸調(diào)用*/ }}例

漢諾(Hanoi)塔問題

A B Chanio(n個(gè)盤，A→B，C為過渡){if(n==1)

直接把盤子A→Belse{hanio(n-1個(gè)盤，A→C，B為過渡)

把n號盤A→B hanio(n-1個(gè)盤，C→B，A為過渡) }}

源程序

/*搬動n個(gè)盤，從a到b，c為中間過渡*/voidhanio(intn,chara,charb,charc){if(n==1)printf("%c-->%c\n",a,b);else{hanio(n-1,a,c,b);printf("%c-->%c\n",a,b);hanio(n-1,c,b,a);}}intmain(void){intn;printf("inputthenumberofdisk:");scanf("%d",&n);printf("thestepsfor%ddiskare:\n",n);hanio(n,'a',‘b',‘c');return0;}inputthenumberofdisk:3t