Python 算法之递归与尾递归，斐波那契数列以及汉诺塔的实现_尾递归写汉诺塔

---

递归概念

递归：程序调用自身的编程技巧称为递归（ recursion）。用一种通俗的话来说就是自己调用自己，它通常把一个大型复杂的问题层层转化为一个与原问题相似的、但是规模较小的问题来求解，当问题小到一定规模的时候，需要一个递归出口返回。递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。

递归函数：在编程语言中，函数直接或间接调用函数本身，则该函数称为递归函数；在数学上的定义如下：对于某一函数 $f(x)$，其定义域是集合 A，那么若对于 A 集合中的某一个值 $X_0$，其函数值 $f(x_0)$ 由 $f(f(x_0))$ 决定，那么就称 $f(x)$ 为递归函数。

---

递归要素

• 递归必须包含一个基本的出口（结束条件），否则就会无限递归，最终导致栈溢出；

• 递归必须包含一个可以分解的问题，例如要想求得 $fact(n)$，就需要用 $n\ast fact(n-1)$；

• 递归必须必须要向着递归出口靠近，例如每次递归调用都会 $n-1$，向着递归出口 $n==0$ 靠近。

---

递归与迭代的区别

• 递归（recursion）：递归则是一步一步往前递推，直到递归基础，寻找一条路径， 然后再由前向后计算。（A调用A）

• 迭代（iteration）：迭代是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。每一次对过程的重复称为一次“迭代”，而每一次迭代得到的结果会作为下一次迭代的初始值，因此迭代是从前往后计算的。（A重复调用B）

---

示例一：阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且 0 的阶乘为 1。即 $n!=1\times 2\times 3\times ...\times (n-1)\times n$，以递归方式定义：$n!=(n-1)!\times n$

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
1
2
3
4
5

---

示例二：斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。

有一个数列：0、1、1、2、3、5、8、13、21、34、55、89…，这个数列从第3项开始，每一项都等于前两项之和。以递推的方法定义：$F(n)=F(n-1)+F(n-2)（n\ge 3，n\in N^{\ast }）$

def fibonacc(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacc(n-1) + fibonacc(n-2)
1
2
3
4
5

以上方法的时间复杂度为$O(2^n)$，稍微大一点的数都会算很久，有一个简单的解决方案，使用 lru_cache 缓存装饰器，缓存一些中间结果：

from functools import lru_cache

# 缓存斐波那契函数已经计算出的结果，最多占用1024字节内存
@lru_cache(maxsize=1024)
def fibonacc(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fibonacc(n-1) + fibonacc(n-2)
1
2
3
4
5
6
7
8
9

另外还有更加节省时间和空间的方法：

def fibonacc(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fibonacc(n-1, next, current+next)
1
2
3
4
5

---

示例三：汉诺塔问题

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。64片黄金圆盘移动完毕之日，就是世界毁灭之时。

对于 n 个盘子，移动步骤如下：

• 把 n-1 个盘子由 A 经过 C 移动到 B
• 把最后一个盘子移动到 C
• 把 n-1 个盘子由 B 经过 A 移动到 C

递归代码实现：

def hanoi(n, a, b, c):                                # n 个盘子，a，b，c三个柱子
    if n > 0:
        hanoi(n-1, a, c, b)                           # 把 n-1 个盘子由 a 经过 c 移动到 b
        print('moving from {0} to {1}'.format(a, c))  # 把最后一个盘子移动到 c
        hanoi(n-1, b, a, c)                           # 把 n-1 个盘子由 b 经过 a 移动到 c
1
2
3
4
5

示例：

def hanoi(n, a, b, c):
    if n > 0:
        hanoi(n-1, a, c, b)
        print('moving from {0} to {1}'.format(a, c))
        hanoi(n-1, b, a, c)


hanoi(3, 'A', 'B', 'C')
1
2
3
4
5
6
7
8

moving from A to C
moving from A to B
moving from C to B
moving from A to C
moving from B to A
moving from B to C
moving from A to C
1
2
3
4
5
6
7

---

尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。通俗来讲就是递归调用放在了函数的最后。

# 一般递归
def func(n):
    if n > 0:
        func(n-1)
        print(n)


# 一般递归
def func(n):
    if n > 0:
        return func(n-1) + n


# 尾递归
def func(n):
    a = n
    if n > 0:
        a += 1
        print(a, n)
        return func(n-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

对于普通的递归，每一级递归都产生了新的局部变量，必须创建新的调用栈，随着递归深度的增加，创建的栈越来越多，容易造成爆栈。

def normal_recursion(n):
    if n == 1:
        return 1
    else:
        return n + normal_recursion(n-1)
1
2
3
4
5

normal_recursion(5) 执行：

normal_recursion(5)
5 + normal_recursion(4)
5 + 4 + normal_recursion(3)
5 + 4 + 3 + normal_recursion(2)
5 + 4 + 3 + 2 + normal_recursion(1)
5 + 4 + 3 + 3
5 + 4 + 6
5 + 10
15
1
2
3
4
5
6
7
8
9

尾递归基于函数的尾调用，每一级调用直接返回递归函数更新调用栈，没有新局部变量的产生，类似迭代的实现。

def tail_recursion(n, total=0):
    if n == 0:
        return total
    else:
        return tail_recursion(n-1, total+n)
1
2
3
4
5

normal_recursion(5) 执行：

tail_recursion(5, 0)
tail_recursion(4, 5)
tail_recursion(3, 9)
tail_recursion(2, 12)
tail_recursion(1, 14)
tail_recursion(0, 15)
15
1
2
3
4
5
6
7

在 Python，Java，Pascal 等语言中是无法实现尾递归优化的，所以采用了 for，while，goto 等特殊结构以迭代的方式来代替尾递归。

---

Python 中尾递归的解决方案

使用普通的递归来实现斐波那契数列的计算，代码段如下：

def fibonacc(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fibonacc(n-1, next, current+next)


a = fibonacc(1000)
print(a)
1
2
3
4
5
6
7
8
9

此时会报错，因为超过了最大递归深度（默认深度900-1000左右）：

Traceback (most recent call last):
  File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 57, in <module>
    a = fibonacc(1000)
  File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 47, in fibonacc
    return fibonacc(n-1, next, current+next)
  File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 47, in fibonacc
    return fibonacc(n-1, next, current+next)
  File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 47, in fibonacc
    return fibonacc(n-1, next, current+next)
  [Previous line repeated 995 more times]
  File "F:/PycharmProjects/algorithm/fibonacc_test.py", line 44, in fibonacc
    if n == 0:
RecursionError: maximum recursion depth exceeded in comparison
1
2
3
4
5
6
7
8
9
10
11
12
13

如果是递归深度不是很大的情况，可以手动重设递归深度来解决：

import sys
sys.setrecursionlimit(10000)  # 递归深度设置为 10000
1
2

如果递归深度非常大，那么就可以采用尾递归优化，但是 Python 官方是并不支持尾递归的（不知道为啥），然而这难不到广大的程序员们，早在 2006 年 Crutcher Dunnavant 就想出了一个解决办法，实现一个 tail_call_optimized 装饰器，原文链接：https://code.activestate.com/recipes/474088/，原代码是 Python 2.4 实现的，用 Python 3.x 实现如下：

# This program shows off a python decorator
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.

import sys


class TailRecurseException(BaseException):
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs


def tail_call_optimized(g):
    """
    This function decorates a function with tail call
    optimization. It does this by throwing an exception
    if it is it's own grandparent, and catching such
    exceptions to fake the tail call optimization.

    This function fails if the decorated5
    function recurses in a non-tail context.
    """
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException as e:
                    args = e.args
                    kwargs = e.kwargs

    func.__doc__ = g.__doc__
    return func
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

使用该装饰器再来实现比较大的斐波那契数列的计算：

@tail_call_optimized
def fibonacc(n, current=0, next=1):
    if n == 0:
        return current
    else:
        return fibonacc(n-1, next, current+next)


a = fibonacc(1000)
print(a)
1
2
3
4
5
6
7
8
9
10

输出结果：

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
1

tail_call_optimized 实现尾递归优化的原理：当递归函数被该装饰器修饰后，递归调用在装饰器while循环内部进行，每当产生新的递归调用栈帧时，f.f_back.f_back.f_code == f.f_code: 就捕获当前尾调用函数的参数，并抛出异常，从而销毁递归栈并使用捕获的参数手动调用递归函数，所以递归的过程中始终只存在一个栈帧对象，达到优化的目的。

---

这里是一段防爬虫文本，请读者忽略。
本文原创首发于 CSDN，作者 TRHX•鲍勃。
博客首页：https://itrhx.blog.csdn.net/
本文链接：https://itrhx.blog.csdn.net/article/details/109322815
未经授权，禁止转载！恶意转载，后果自负！尊重原创，远离剽窃！
1
2
3
4
5