递归算法.
本节我们先来了解一下递归算法.
递归算法的基本原理:
说到递归算法,就不得不提到栈.当程序执行到递归函数的时候,将函数进行入栈操作,在入栈之前,通常需要完成3件事.
1.将所有实参,返回地址等信息传递给被调函数储存
2.为被调函数的局部变量分配储存区
3.将控制转移到被调函数入口
当一个函数完成之后会进行出栈操作,出栈之前同样要完成三件事:
1.保存被调函数的计算结果
2.释放被调函数的数据区
3.依照被调函数保存的返回地址将控制转移到调用函数
递归的整个过程都需要借助栈来完成,每当执行一个函数,就在栈分配空间,函数推出后,释放栈顶空间
递归算法一般包含三要素:递归前阶段,递归返回阶段和终止条件.递归前阶段是指在递归函数内执行什么样的操作以进入下一层嵌套;递归返回段是指本层执行递归函数需要返回给上层的数据,存在无需返回数据给上层的情形;终止条件是指递归函数在何种条件下终止对自身的调用,结束整个递归过程.