栈与递归递归与回溯广义表

《栈与递归递归与回溯广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈与递归递归与回溯广义表第五章递归一、栈和递归递归定义递归函数递归定义先定义最基本的概念再用已定义的概念定义新的概念例命题演算公式的定义（1）单个命题变元符号是命题（2）如果A,B是命题，则(┐A),(A∧B),(A∨B),(A→B),（A←→B)都是公式递归定义先定义最基本的概念再用已定义的概念定义新的概念例标识符的定义（1）单个英文字母是标识符（2）标识符后缀一个数字或一个英文字母是标识符递归函数的定义一个算法可以分解成若干相同的小算法分解到某简单的子算法时终止有一个或几个终止条件递归：由其前面的值求当前值递归必须导致终止条件递归函数的例例函数xnx0=1xn=x*xn-1n>0

2、xn=xn-1/xn<0例函数n!0!=1n!=n*(n-1)!n>0递归函数的例函数C(n,m)C(0,m)=1,C(m,m)=1.C(n,m)=C(n-1,m-1)+C(n,m-1)#include//computen!=n*(n-1)*(n-2)...(2)(1),0!=1recursivelylongFactorial(longn){//ifn==0,then0!=1;otherwise,n!=n*(n-1)!if(n==0)return1;elsereturnn*Factorial(n-1);}voidmain(void){inti,n;//ente

3、r4positiveintegersandcomputen!foreachcout<<"Enter4positiveintegers:";for(i=0;i<4;i++){cin>>n;cout<Enter4positiveintegers:07140!=17!=50401!=14!=24*/阶乘堆栈主程序参数44*Factorial(3)参数33*Factorial(2)参数22*Factorial(1)参数11*Factorial(0)参数0Factorial(0)112624递归函数先操作后遍历例voi

4、dFucnc(charch){if(ch<=‘z’){cout<

5、rstuvwxyzzyxwvutsrqponmlkjihgfedcba递归函数遍历操作遍历例voidFucnc(charch){if(ch<=‘d’){Func(ch+1);cout<

6、1)+1+F(n-1)=2*F(n-1)+1F(n)+1=2*(F(n-1)+1)=22*(F(n-2)+1)=······=2n-1*(F(1)+1)=2nF(n)=2n-1河内塔问题程序#include#pragmahdrstop#include"strclass.h"//movendisksfromstartpegtoendpeg,//usingmiddlepegastheintermediatepegvoidhanoi(intn,charA,charB,charC){if(n==1)cout<<“move”<

7、anoi(n-1,A,C,B);cout<<“move”<>n;cout<<"Thesolutionforn="<Enterthenumber