3.2.5递归函数程序设计 - 递归函数程序设计-专题辅导课件

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,