图解递归算法-清晰易懂

什么是递归？

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

简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归。

递归的两个必要条件 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):
   if n == 1:
       return 1
   else:
       return n * self.func(n - 1)

可视化直观表示即：

递归其实可以看做两部分操作，一步步去寻求子问题的解（直到满足限制条件，如n==1，得f(1)=1）是“递”；得到最基本的子问题的解之后，再一步步返回求上一层的解是“归”。

（如上图，“递”的过程中，f(n)=n*f(n-1)，结果值都是基于子问题的；但是，到最基本的问题之后，得到了解，“归”的过程中，每一步都有确定的返回值，直到一层层返回结束，得解。）

因为，函数的递归要利用到“栈”，下图以“栈”的方式展现“递归”过程：

“递”的过程会将函数的地址、参数等压栈（push）保存（以便“归”的时候找到之前执行到的位置），最基本子问题（f(1)=1）求解之后，再一步步“归”，此过程中，会发生出栈（pop）操作，函数调用结束后，栈顶释放。

将两个过程用函数打印出来看一下：

def func(n):
    print "递：%d "%n,
    if n==1:
        res = 1
    else:
        res = n*func(n-1)
    print "归:%d "%res,
    return res

func(4)

结果：

超简洁图解

如果上述两个图示还不够清晰的话，请看第三个：

我们将函数的递归调用看做微机原理中的“中断响应”;

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

如打印一个链表：

# 递归打印链表
    def printListNode(self,lst):
        if not lst:
            return
        # print lst.val,
        self.printListNode(lst.next)
        print lst.val,

print在递归调用之后，则结果(假如单向无环链表[1,2,3,4])：

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

# 递归打印链表
    def printListNode(self,lst):
        if not lst:
            return
        print lst.val,
        self.printListNode(lst.next)
        # print lst.val,

print在递归调用之后，则结果(假如单向无环链表[1,2,3,4])：

附：

二叉树的先序、中序、后序遍历之所以得到那样的结果，也是因函数中print的位置在调用递归的前后位置不同造成的。

另外，leetcode中的一道题目也很类似：