递归以及Python尾递归优化

递归

每个递归函数都有两部分：
1. 基线条件
一个或多个结束条件(if)，不再调用函数自身，从而避免无限递归
2. 递归条件
调用函数自身func()

递归与循环抉择

使用循环，程序的性能可能更高；使用递归，程序可能更容易理解。
如何选择要看什么对你来说更重要。

汉罗塔(hanoi)问题

def hanoi(n, a, b, c):
    """
    n个盘子（最终移动到C）：
        1. 把n-1个盘子从A通过C移动到B
        2. 把n个盘子从A移动到C
        3. 把n-1个盘子从B通过A移动到C
        汉罗塔移动次数的递推式：h(x) = 2h(x-1)+1
        h(64) = 18446744073709551615  --> 2^n
        假设婆罗门每秒移动一个盘子，则总共需要5800亿年！
    :param n:
    :param a:
    :param b:
    :param c:
    :return:
    """
    if n > 0:
        hanoi(n-1, a, c, b)
        print(f'Moving from {a} to {c}')
        hanoi(n-1, b, a, c)


hanoi(3, 'A', 'B', 'C')

尾递归

Python中的函数是通过栈结构实现的，
上一层（接近栈底）与下一层（接近栈顶）（自我的理解）之间只有调用关系，不涉及运算。

尾递归优化

Python中默认的递归深度为1000。
如果相互之间只有调用关系，就可以让上一层（接近栈底）出栈，可以避免调用栈溢出

代码示例

#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""递归

每个递归函数都有两部分：
1. 基线条件
   一个或多个结束条件(if)，不再调用函数自身，从而避免无限递归
2. 递归条件
   调用函数自身func()

使用循环，程序的性能可能更高；使用递归，程序可能更容易理解。
如何选择要看什么对你来说更重要。

尾递归：
Python中的函数是通过栈结构实现的，
上一层（接近栈底）与下一层（接近栈顶）（自我的理解）之间只有调用关系，不涉及运算。

尾递归优化：
Python中默认的递归深度为1000.
如果相互之间只有调用关系，就可以让上一层（接近栈底）出栈，可以避免调用栈溢出
"""
import sys
from functools import wraps


class TailCallOptimizedError(Exception):

    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs


def tail_call_optimized(ori_func):
    @wraps(ori_func)
    def wrapper(*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 TailCallOptimizedError(args, kwargs)
        else:
            while 1:
                try:
                    return ori_func(*args, **kwargs)
                except TailCallOptimizedError as error:
                    args = error.args
                    kwargs = error.kwargs
    return wrapper


@tail_call_optimized
def factorial(n, acc=1):
    if n == 0:
        return acc
    return factorial(n - 1, n * acc)


print(factorial(10000))