递归函数--递归、尾递归

递归函数–递归，尾递归

函数在内部可以调用其他函数，也可以自己调用自己，自己调用自己的函数叫递归函数。

例子一：

如：

python
def fact(n):
    if n==1:
        return 1        
     #n * fact(n-1)中，当n=1时(n-1)=0，为了避免n=1时出错，直接让n=1时返回1
    return n * fact(n-1)

假设这里n=5,即 def fact(5)：

这个函数的执行过程是：先调用fact函数的返回值：n * fact(n-1)

fact(5) ==>n * fact(n-1)，==> 5 * fact(5 - 1) ==> 5 * fact(4)

这里fact（4）再次调用fact函数，即将算式中的fact(4)替换成返回值

fact(4) ==>n * fact(n-1)，==>5 * (4 * fact(4 - 1)) ==> 5 * (4 * fact(3))

以此类推，直到算式中没有fact()函数

fact(3) ==>n * fact(n-1)，==>5 * (4 * (3 * fact(3-1))) ==> 5 * (4 * (3 * fact(2)))

fact(2) ==>n * fact(n-1)，==>5 * (4 * (3 * (2 * fact(2-1)))) ==> 5 * (4 * (3 * (2 * fact(1))))

fact(1) ==>n * fact(n-1)，==>5 * (4 * (3 * (2 * (2-1)))) ==> 5 * (4 * (3 * (2 * fact(1))))

n = 1的是时，return 1 ，所以最终是：5 * (4 * fact(3 * fact(2 * 1)))

因此fact(1) ==>n * fact(n-1)，==>5 * (4 * (3 * (2 * (2-1)))) ==> 5 * (4 * (3 * (2 * 1)))

即 5 * 4 * 3 * 2 * 1 = 5!=120

例子二：

尾递归

def fact(n):
    print(fact_iter(n, 1))
    return fact_iter(n, 1)


def fact_iter(num, product):
    if num == 1:
        return product                
    #在这里打印可以看到递归（循环）的次数
    return fact_iter(num - 1, num * product)


if __name__ == "__main__":
    fact(3)