3.2.5遞歸函數(shù)程序設(shè)計(jì) - 遞歸函數(shù)程序設(shè)計(jì)-專(zhuān)題輔導(dǎo)課件

C程序設(shè)計(jì)專(zhuān)題輔導(dǎo)課

遞歸函數(shù)程序設(shè)計(jì)遞歸函數(shù)函數(shù)直接或間接地調(diào)用自己的形式稱(chēng)為函數(shù)的遞歸調(diào)用。遞推法與遞歸法求階乘遞推法n!=1*2*3*....*nfor(result=1,i=1;i<=n;i++)result=result*i;遞歸法遞歸定義n!=n*(n-1)!(n>1)n!=1(n=0,1)遞歸函數(shù)fact(n)程序解析例10-3用遞歸函數(shù)求n!。#include<stdio.h>doublefact(intn)；int

main(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;}求n!遞歸定義n!=n*(n-1)!(n>1)n!=1(n=0,1)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)過(guò)程fact(3)=

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

i=1i=1遞歸最終能結(jié)束(遞歸出口)兩個(gè)條件缺一不可解決遞歸問(wèn)題的兩個(gè)著眼點(diǎn)遞歸函數(shù)可以用數(shù)學(xué)歸納法來(lái)理解數(shù)學(xué)歸納法：首先證明初值成立，然后假設(shè)n時(shí)成立，再證明n+1時(shí)成立，則問(wèn)題得到證明。例10-4寫(xiě)輸出結(jié)果#include<stdio.h>longfib(intg){switch(g){case1:case2:return(1);}return(fib(g-1)+fib(g-2));}voidmain(){longk;k=fib(5);

printf("k=%ld\n",k);}fib(g)=1g=1fib(g)=1g=2fib(g)=fib(g-1)+fib(g-2)g>=3k=5Fibonacci數(shù)列遞歸公式遞歸式遞歸出口例10-5漢諾(Hanoi)塔將64個(gè)盤(pán)從座A搬到座B(1)一次只能搬一個(gè)盤(pán)子(2)盤(pán)子只能插在A、B、C三個(gè)桿中(3)大盤(pán)不能壓在小盤(pán)上

A B C分析

A B C

A B Cnn-1函數(shù)

/*搬動(dòng)n個(gè)盤(pán)，從a到b，c為中間過(guò)渡*/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);}}hanio(n個(gè)盤(pán)，A→B)//C為過(guò)渡{if(n==1)直接把盤(pán)子A→Belse{hanio(n-1個(gè)盤(pán),A→C)

把n號(hào)盤(pán)A→B hanio(n-1個(gè)盤(pán),C→B) }}算法八皇后問(wèn)題八皇后問(wèn)題是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型例題。該問(wèn)題是著名的數(shù)學(xué)家高斯提出：在8X8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線(xiàn)上，問(wèn)有多少種擺法。11111111八皇后問(wèn)題分析：任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線(xiàn)上，可用數(shù)組a記錄各行皇后所在的列，數(shù)組b,c反映兩條斜線(xiàn)上是否安全。0123456701234567b數(shù)組C數(shù)組八皇后問(wèn)題#include<stdio.h>#defineN8/*定義列數(shù)*/int

a[N]={0};intb[2*N-1]={0};intc[2*N-1]={0};int

q[N][N]={0};intcount=0;voidqueen(intn){intj;for(j=0;j<N;j++)/*對(duì)第n行進(jìn)行第n個(gè)皇后的位置確定*/if(a[j]==0&&b[n+j]==0&&c[n-j+N-1]==0){/*可以作皇后候選位置*/

q[n][j]=1;a[j]=1;b[n+j]=1;c[n-j+N-1]=1;/*皇后占領(lǐng)的位置標(biāo)記*/

if(n==N-1)print();elsequeen(n+1);

q[n][j]=0;a[j]=0;b[n+j]=0;c[n-j+N-1]=0;}}voidmain(){queen(0);}voidprint(){int

i,j;for(i=0;i<N;i++){for(j=0;j<N;j++)

printf("%d",q[i][j]);printf("\n");}

printf("---------%d-------\n“,++count);}遞歸算法遞歸算法往往有著算法簡(jiǎn)單，容易理解，可讀性好的優(yōu)點(diǎn)，但執(zhí)行效率不高。如果存在較明確的遞推算法時(shí)，遞推算法執(zhí)行效率較高。典型：Fibonacci數(shù)列遞歸算法效率非常低Fibonacci數(shù)列遞歸程序效率fib(5)fib(4)fib(3)fib(2)fib(1)fib(3)fib(2)fib(2)fib(1)fib(6)fib(4)fib(3)fib(2)fib(2)fib(1)fib(g)=1g=1fib(g)=1g=2fib(g)=fib(g-1)+fib(g-2)g>=3用遞歸方法實(shí)現(xiàn)對(duì)一個(gè)整數(shù)進(jìn)行逆序輸出。voidreverse(intn){if(n/10==0)

printf("%d",n);else{printf("%d",n%10);reverse(n/10);}}voidreverse(intn){if(n/10==0)

printf("%d",n);else{reverse(n/10);printf("%d",n%10);}}該函數(shù)的功能？2008試題B#include<stdio.h>voidfun(intn,