递归函数

本质:自己调用自己

递归特性

1. 必须有一个明确的结束条件

2. 每次进入更深一层递归时，问题规模相比上次递归都应有所减少

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

递归计算n的阶乘

#!/usr/bin/env python
# -*- coding:utf-8 -*-
def jiecheng(n):
    if n == 1:
        return 1
    return n*jiecheng(n-1)

print(jiecheng(10))

问题

当递归次数超过999会报错

RecursionError: maximum recursion depth exceeded in comparison

尾递归优化

#!/usr/bin/env python
# -*- coding:utf-8 -*-
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

@tail_call_optimized
def zs_sum(n, acc=1):
    if n == 1:
        return acc
    return zs_sum(n - 1, n + acc)

print(zs_sum(100))


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


print(zs_sum(1000))
print(factorial(1000))