递归和深拷贝

递归

在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

递归实例:汉诺塔

def move(n, home="A柱", destination="C柱", assistance="B柱"):
    if n == 1:
        print("\t将" + home + "的最上面的环移动到" + destination + "的最上面")
    if n > 1:
        move(n - 1, home, assistance, destination)
        move(1, home, destination, assistance)
        move(n - 1, assistance, destination, home)


move(1)
# 将A柱的最上面的环移动到C柱的最上面
move(2)
# 将A柱的最上面的环移动到B柱的最上面
# 将A柱的最上面的环移动到C柱的最上面
# 将B柱的最上面的环移动到C柱的最上面
move(3)
# 将A柱的最上面的环移动到C柱的最上面
# 将A柱的最上面的环移动到B柱的最上面
# 将C柱的最上面的环移动到B柱的最上面
# 将A柱的最上面的环移动到C柱的最上面
# 将B柱的最上面的环移动到A柱的最上面
# 将B柱的最上面的环移动到C柱的最上面
# 将A柱的最上面的环移动到C柱的最上面

写一个装饰器来探究这个函数开辟了多少个作用域吧

def foo(func):
    step = 0

    def wrapper(*args, **kwargs):
        nonlocal step
        step += 1
        print("第%s个函数作用域被开辟" % step)
        res = func(*args, **kwargs)
        print("第%s个函数作用域被销毁" % step)
        step -= 1
        return res

    return wrapper


@foo
def move(n, home="A柱", destination="C柱", assistance="B柱"):
    if n == 1:
        print("\t将" + home + "的最上面的环移动到" + destination + "的最上面")
    if n > 1:
        move(n - 1, home, assistance, destination)
        move(1, home, destination, assistance)
        move(n - 1, assistance, destination, home)


move(1)
# 第1个函数作用域被开辟
#    将A柱的最上面的环移动到C柱的最上面
# 第1个函数作用域被销毁
move(2)
# 第1个函数作用域被开辟
# 第2个函数作用域被开辟
#    将A柱的最上面的环移动到B柱的最上面
# 第2个函数作用域被销毁
# 第2个函数作用域被开辟
#    将A柱的最上面的环移动到C柱的最上面
# 第2个函数作用域被销毁
# 第2个函数作用域被开辟
#    将B柱的最上面的环移动到C柱的最上面
# 第2个函数作用域被销毁
# 第1个函数作用域被销毁

尾递归

尾递归是指，在函数返回的时候，调用自身本身，并且，return 语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

# 一般递归
def normal_recursion(n):
    if n == 1:
        return 1
    else:
        return n + normal_recursion(n - 1)


# 尾递归
def tail_recursion(n, total=0):
    if n == 0:
        return total
    else:
        return tail_recursion(n - 1, total + n)

最后一步调用,形成"调用栈"
复杂度 O(n) => O(1)
遗憾的是，cpython 没有针对尾递归做优化，即使把上面的函数改成尾递归方式，也会导致栈溢出。 实际上只需要保证函数的调用上下文不变，尾递归就算优化完成，可以实现一个tail_call_optimized 装饰器来对尾递归的函数进行优化

import sys


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


def tail_call_optimized(g):
    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

上述代码借助抛出异常的信息中携带 f_back 来让上下文不变。除此之外也可借助惰性函数的 yield 来不记录前状态实现。

深浅拷贝

浅拷贝

l2 = l1

对于赋值运算来说,2 个列表名,指向的是同一个内存地址，所以他们是完全一样的。

l2 = l1.copy()

对于浅 copy 来说，只是在内存中重新创建了开辟了一个空间存放一个新列表，但是新列表中的元素与原列表中的元素是公用的。

借助 copy 模块

import copy

l2 = copy.deepcopy(l1)

对于深 copy 来说，列表是在内存中重新创建的，列表中可变的数据类型是重新创建的，列表中的不可变的数据类型是公用的。

如果需要自己写一个函数来实现深拷贝，那么可以通过递归实现。

dt = {
    "a": "aaa",
    "b": "bbb",
    "c": {"c1": 11, "c2": {"c21": "211", "c22": "212", "c23": "213"}, "c3": 33},
}


def copy_dict(d):
    res = {}
    if not d:
        return {}
    for key, value in d.items():
        # 如果不是dict字典，则直接赋值
        if not isinstance(value, dict):
            res[key] = value
        # 如果还是字典，递归调用copy_dict(d)
        else:
            res[key] = copy_dict(value)
    return res


print("复制前：" + str(dt))
copy_dt = copy_dict(dt)
print("复制后：" + str(copy_dict(dt)))