3.2.5遞歸函數(shù)程序設計 - 遞歸函數(shù)程序設計-專題輔導課件

C程序設計專題輔導課

遞歸函數(shù)程序設計遞歸函數(shù)函數(shù)直接或間接地調用自己的形式稱為函數(shù)的遞歸調用。遞推法與遞歸法求階乘遞推法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)的實現(xiàn)過程fact(3)=

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

i=1i=1遞歸最終能結束(遞歸出口)兩個條件缺一不可解決遞歸問題的兩個著眼點遞歸函數(shù)可以用數(shù)學歸納法來理解數(shù)學歸納法：首先證明初值成立，然后假設n時成立，再證明n+1時成立，則問題得到證明。例10-4寫輸出結果#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個盤從座A搬到座B(1)一次只能搬一個盤子(2)盤子只能插在A、B、C三個桿中(3)大盤不能壓在小盤上

A B C分析

A B C

A B Cnn-1函數(shù)

/*搬動n個盤，從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);}}hanio(n個盤，A→B)//C為過渡{if(n==1)直接把盤子A→Belse{hanio(n-1個盤,A→C)

把n號盤A→B hanio(n-1個盤,C→B) }}算法八皇后問題八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是著名的數(shù)學家高斯提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。11111111八皇后問題分析：任意兩個皇后都不能處于同一行、同一列或同一斜線上，可用數(shù)組a記錄各行皇后所在的列，數(shù)組b,c反映兩條斜線上是否安全。0123456701234567b數(shù)組C數(shù)組八皇后問題#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++)/*對第n行進行第n個皇后的位置確定*/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;/*皇后占領的位置標記*/

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);}遞歸算法遞歸算法往往有著算法簡單，容易理解，可讀性好的優(yōu)點，但執(zhí)行效率不高。如果存在較明確的遞推算法時，遞推算法執(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用遞歸方法實現(xiàn)對一個整數(shù)進行逆序輸出。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,