递归算法经典实例,递归算法一般利用什么实现

　　什么是递归？在高级语言中，调用自己和其它函数没有本质的不同。我们把一个直接用自己或通过一系列的调用语句间接地调用自己的函数，称作递归函数。每个递归函数必须至少有一个条件，满足时递归不再执行，即不再引用自身而是返回值退出。

　　简单来说，如果函数本身在函数中被调用，这种现象叫做递归。

　　递归的两个必要条件

　　1.有一个限制条件。当满足这个条件时，递归将不再继续。

　　2.在每次递归调用之后，它越来越接近这个限制。

　　插图如下简单示例，我们求一个数n的阶乘：

　　f(n)=n*(n-1)*(n-2) … *2*1

　　显然，这个公式也可以写成：

　　f(n) = n*f(n-1)

　　因为f(n)与f(n-1)相关，也就是基于它的子问题，可以通过递归来求解。

　　Python代码：def func (self，n):如果n==1:返回1否则：返回n * self。func (n-1)形象直观的表示是：

　　事实上，递归可以看作是一个两部分的操作。逐步寻求子问题的解(直到满足约束条件，如n==1，f(1)=1)是“递归”的；在得到最基本的子问题的解之后，再一步一步的往回走，寻找下一级的解，就是“返回”了。

　　(如上图，在“交付”的过程中，f(n)=n*f(n-1)，结果值都是基于子问题的；但是，当我们到了最基本的问题，我们知道在“回归”的过程中，每一步都有一个确定的回归值，直到每一层回归结束，我们才能得到解。)

　　由于函数的递归需要利用“栈”，下图以“栈”的形式展示了“递归”的过程：

　　在“交付”的过程中，会推送并保存函数的地址和参数(以便“返回”时找到之前执行的位置)。最基本的子问题(f(1)=1)解决后，会一步步“回归”。在这个过程中会发生pop操作，调用函数后会释放栈顶。

　　用函数把这两个过程打印出来看看：

　　def func(n):print delivery:% d % n，if n==1:RES=1 else:RES=n * func(n-1)print return:% d % RES，return resfunc(4) Result:

　　超简洁插画如果上面两个插画不够清晰，请看第三个：

　　我们把函数的递归调用看作微机原理中的“中断响应”；

　　假如图中“圆环”代表print，且其位于递归调用之后(类似中断响应的断点之后)，那么最后调用的反而最先print！（根据函数的执行流程，即图中的箭头方向）[类似于栈LIFO].

　　比如打印一个链表：

　　#递归打印链表def printlistnode (self，lst):如果不是lst:返回# printlst.val，self。printlistnode(lst . next)printlst . val，递归调用后打印，结果(如果单向非循环链表[1，2，3，4]):

　　（如果print在断点之前，则完全相反！）

　　#递归打印链表def printlistnode (self，lst):如果不是lst:返回printlst.val，self。printlistnode(lst . next)# printlst . val，递归调用后打印，结果(如果单向非循环链表[1，2，3，4]):

　　附：

　　二叉树的第一个、中间和最后一个遍历是由递归前后函数中print的不同位置产生的。

　　另外，leetcode中的一个题目也类似：https://leet code-cn . com/problems/binary-tree-level-order-traverse-ii/

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。