首页 > 代码库 > 【人生苦短 PYTHON当歌】——PYTHON函数式编程03

【人生苦短 PYTHON当歌】——PYTHON函数式编程03

Python递归                                                                          

如果一个函数在内部调用函数自身,这个函数就是递归函数;

下面看一个经典例子:利用Python递归求阶乘

def fact(j):
    sum=0
    if j==0:
        sum=1
    else:
        sum=j*fact(j-1)
    return sum
for i in range(5):
    print(%d!=%d%(i,fact(i)))

经过CPS变换消除general recursion,

id=lambda x:x
def factCPS(n):
    def f(n,k):
        if n==0:
            return k(1)
        else:
            return f(n-1,lambda x:k(n*x))
    return f(n,id)

尾递归优化                           

尾递归基于函数的尾调用,每一级调用直接返回函数的返回值更新调用栈,而不用创建新的调用栈,类似迭代的实现,时间和空间上优化了一般递归;

def fact(n,sum=0)
    if n==0:
        return sum
    else:
        return fact(n-1,sum+n)

 

【人生苦短 PYTHON当歌】——PYTHON函数式编程03