13函数递归.pptx

递归生活中的递归现象？1.两块镜子，镜面相对，镜子里面会出现什么情况？2.将你家电脑上的摄像头对电脑屏幕，打开摄像头软件，想想摄像头会拍到什么样画面？数学里的递归定义自然数:① 1 是自然数。②任何自然数加上 1 还是自然数。N是不是自然数？因为1-2-3-4-…………- N-2 - N-1 -N一、递归概念 当函数的定义中，又直接或间接地出现对自身的调用，则称这样的程序嵌套定义为递归定义。 递归通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解. 在程序中，递归是通过函数的调用来实现的。函数直接调用其自身，称为直接递归；函数间接调用其自身，称为间接递归。void A(){ B();}void B(){ A();}void f(int n){ …… f(n-1); ……}例1 阶乘函数 阶乘函数可递归地定义为：边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。#includeiostreamusing 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; }函数调用过程中内存的变化程序必须在内存中运行，一个程序所占内存通常分为3块。代码区，全局数据区，栈区代码区：存放二进制代码，所有函数的代码都保存在这里。全局数据区：在main函数外，定义的变量和数组。栈区： 一个程序往往由一个或多个函数组成，每个函数在运行的时候，都会在栈区内得到一块连续的，大小合适的存储区域，当函数执行完，该内存块空间被释放。栈区栈区是一块连续的内存空间，因为它的操作方式与一种名为“栈”的数据结构相似，所以才称为“栈区”栈区内 最后分配的空间，一定最先释放 而最先分配的空间，则最后释放Int main(){ coutfac(5)endl; return 0; }Int fac(int n){ int p;① if(n==1)p=1; else {② int t=fac(n-1);③ p=n*t; }④ return p;}栈区的变化：fac(1) n=1p执行位置：Main函数fac(4) n=4p执行位置：fac(3) n=3p执行位置：fac(2) n=2p执行位置：fac(5) n=5p执行位置：t=6t=24t=2t=1=4*6=1=1*2=2*3=5*24①②①④④③④②①③①②④③④③②①第五层facmain()第二层fac第三层fac第四层fac第一层facn=4p=4*fac(3)n=5p=5*fac(4)n=3p=3*fac(2)n=2p=2*fac(1)n=1p=1fac(5)Int fac(int n){ int p; if(n==1)p=1; else p=n*f(n-1); return p;}递归层次:输出fac(1)=1fac(5)=120fac(4)=24fac(3)=6fac(2)=2假设调用该递归函数的主函数为第0层，则从主函数调用递归函数为进入第1层；从第 i层递归调用本身为进入“下一层”，即第 i+1 层。反之，退出第 i 层递归应至“上一层”，即第 i-1 层。递归函数的特点：第一：在函数体内，调用自身第二：边界条件，也就是递归的终止条件递归函数的一般写法： if（满足边界条件）{ 计算结果或直接结果。 }Else{ 调用自身，参数的数值变小。}……ABCHanoi问题原型64 古典数学问题。问题描述：古代有个一梵塔，塔内有三根轴A、B、C，开始时A轴上有64个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这64个盘子从A轴移到C轴，但规定每次只允许移动一个盘子，且在移动过程中，3个轴上的盘子始终都是大的在下，小的在上。移动中可以利用B轴。要求写出移动盘子的步骤。ABCABC将三个盘子从A移动到C（1）先将2个紫色的从A移动到B（2）将1个黄色的从A移动到C（3）最后将2个紫色的从B移动到CABC将三个盘子从A移动到C（1）先将2个紫色的从A移动到B（2）将1个黄色的从A移动到C（3）最后将2个紫色的从B移动到CABC将三个盘子从A移动到C（1）先将2个紫色的从A移动到B（2）将1个黄色的从A移动到C（3）最后将2个紫色的从B移动到CABC将三个盘子从A移动到C（1）先将2个紫色的从A移动到B（2）将1个黄色的从A移动到C（3）最后将2个紫色的从B移动到CABC将三个盘子从A移动到C（1）先将2个紫色的从A移动到B（2）将1个黄色的从A移动到C（3）最后将2个紫色的从B移动到CABC将三个盘子从A移动到C（1）先将2