C程序設計專題輔導課

遞歸函數程序設計遞歸函數函數直接或間接地調用自己的形式稱為函數的遞歸調用。遞推法與遞歸法求階乘遞推法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)遞歸函數fact(n)程序解析例10-3用遞歸函數求n!。#include<stdio.h>doublefact(intn)；int

main(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;}求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)}}}遞歸函數fact(n)的實現過程fact(3)=

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

i=1i=1遞歸最終能結束(遞歸出口)兩個條件缺一不可解決遞歸問題的兩個著眼點遞歸函數可以用數學歸納法來理解數學歸納法：首先證明初值成立，然后假設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數列遞歸公式遞歸式遞歸出口例10-5漢諾(Hanoi)塔將64個盤從座A搬到座B(1)一次只能搬一個盤子(2)盤子只能插在A、B、C三個桿中(3)大盤不能壓在小盤上

A B C分析

A B C

A B Cnn-1函數

/*搬動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) }}算法八皇后問題八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是著名的數學家高斯提出：在8X8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。11111111八皇后問題分析：任意兩個皇后都不能處于同一行、同一列或同一斜線上，可用數組a記錄各行皇后所在的列，數組b,c反映兩條斜線上是否安全。0123456701234567b數組C數組八皇后問題#include<stdio.h>#defineN8/*定義列數*/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);}遞歸算法遞歸算法往往有著算法簡單，容易理解，可讀性好的優點，但執行效率不高。如果存在較明確的遞推算法時，遞推算法執行效率較高。典型：Fibonacci數列遞歸算法效率非常低Fibonacci數列遞歸程序效率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用遞歸方法實現對一個整數進行逆序輸出。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);}}該函數的功能？2008試題B#include<stdio.h>voidfun(intn,