《递归解决八皇后以及汉诺塔迷宫源码.doc》由会员分享,可在线阅读,更多相关《递归解决八皇后以及汉诺塔迷宫源码.doc(13页珍藏版)》请在金锄头文库上搜索。
1、149 第6章 递归 假设欲计算出13*4,则:13 * 4 = 13 + ( 13 * 3 )= 13 + ( 13 + ( 13 * 2 ) )= 13 + ( 13 + ( 13 + ( 13 * 1 ) ) )= 13 + ( 13 + ( 13 + 13 ) )= 13 + ( 13 + 26 )= 13 + 39 = 52程序源代码:010203040506070809101112131415161718192021222324252627282930313233343536373839/* = Program Description =*/* 程序名称: multiply.c *
2、/* 程序目的: 设计一个可计算两数相乘,但仅用加法运算, */* 不使用乘法运算的程序。 */* Written By (WANT Studio.) */* = */* - */* 递归乘法运算 */* - */int Multiply(int M,int N)intResult; /*运算结果*/if ( N = 1)Result = M; /* 递归结束条件*/ElseResult = M + Multiply(M,N-1);/* 递归执行部分 */returnResult;/* - */* 主程序 */* - */void main ()intNumA;/* 乘数变量*/intNumB
3、;/* 被乘数变量*/intProduct;/* 乘积变量 */printf(Please enter Number A:);/* 输入乘数*/scanf(%d,&NumA);printf(Please enter Number B:);/* 输入被乘数*/scanf(%d,&NumB);Product = multiply(NumA,NumB);printf(%d * %d = %d,NumA,NumB,Product);运行结果:C:DSmultiplyPlease enter Number A:13Please enter Number B:413 * 4 = 52C:DS我们由题意可知
4、每次执行的过程相似,唯一的不同点为其中一个传入参数,每次执行都递减。递归结束条件为当被乘数为1时返回乘数的值。否则继续调用程序并递减传入被乘数值。其结构如下:int Multiply(int M,int N)intResult;if ( N = 1)Result = M;/* 递归结束条件(Stopping Case) */else Result = M + Multiply(M,N-1);/* 递归执行部分(Recursive Step) */ returnResult;处理递归问题,常采用if语句来判断是否符合递归结束条件,其算法格式如下:if (符合递归结束条件)then返回 答案els
5、e使用递归将程序分割为更简单的小程序。在C语言中,我们采用堆栈这个数据结构来记录函数调用后的返回地址。例如有一个程序如下:intProcedureA ()/*子程序A*/ProcedureB();/*调用子程序B*/*返回地址2 */intProcedureB()/*子程序B */void main ()/*主程序 */ProcedureA();/*调用子程序A */*返回地址1 */程序源代码:0102030405060708091011121314151617181920212223242526272829303132333435/* = Program Description = */*
6、 程序名称: reverse.c */* 程序目的: 运用递归设计一个将字符串反转的程序。 */* Written By . (WANT Studio.) */* = */charString30;/* 声明字符串变量*/intLength;/* 字符串长度变量 */* - */* 递归字符串反转 */* - */void Reverse(int N)if ( N reversePlease enter string : ABCThe reverse string : CBAC:DS程序源代码:01020304050607080910111213141516171819202122232425262728293031/* = Program Description = */* 程序名称: factor.c */* 程序目的: 运用递归设计一个做阶乘运算的程序。 */* Written By . (WANT Studio.) */* =*/* - */* 递归阶层运算 */* - */int Factor(int N)if ( N = 1) /* 递归结束条件 */return 1;elsereturn N * Factor(N-1);/* 递归执行部分 */* - */* 主程序 */* - */void main ()intNumber;