13函数的递归.pptx

递归;生活中的递归现象？;数学里的递归;一、递归概念 当函数的定义中，又直接或间接地出现对自身的调用，则称这样的程序嵌套定义为递归定义。 递归通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解. ;void f(int n) { …… f(n-1); …… };例1 阶乘函数 阶乘函数可递归地定义为：;#includeiostream using namespace std; int fac(int n) { int p; if(n==1)p=1; else { p=n*fac(n-1); } return p; } int main() { coutfac(5)endl; return 0; };函数调用过程中内存的变化;栈区; Int main() { coutfac(5)endl; return 0; } ;;递归函数的特点： 第一：在函数体内，调用自身 第二：边界条件，也就是递归的终止条件;递归函数的一般写法： if（满足边界条件） { 计算结果或直接结果。 } Else { 调用自身，参数的数值变小。 }; 古典数学问题。问题描述：古代有个一梵塔，塔内有三根轴A、B、C，开始时A轴上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A轴移到C轴，但规定每次只允许移动一个盘子，且在移动过程中，3个轴上的盘子始终都是大的在下，小的在上。移动中可以利用B轴。要求写出移动盘子的步骤。;;;;;;;;;;;;;;（1）先将2个紫色的从A移动到B （2）将1个黄色的从A移动到C （3）最后将2个紫色的从B移动到C;;;;;;;;;;;;（1）先将2个紫色的从A移动到B （2）将1个黄色的从A移动到C （3）最后将2个紫色的从B移动到C;;;;;;;;;;;（1）先将2个紫色的从A移动到B （2）将1个黄色的从A移动到C （3）最后将2个紫色的从B移动到C;思考： 如果有4个盘子要怎么移呢？5个盘子呢？;;Hanoi(int n,char x,char y,char z);void Hanoi(int n,char x,char y,char z) { if(n==1) coutx-zendl; else { Hanoi(n-1,x,z,y); coutx-zendl; Hanoi(n-1,y,x,z); } } int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };int main() { Hanoi(3,A,B,C); return 0; };1202: 2的幂次方