python的递归算法学习（1）

递归函数
在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。
举个例子，我们来计算阶乘 n! = 1 * 2 * 3 * ... * n，用函数 fact(n)表示，可以看出：
fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n
所以，fact(n)可以表示为 n * fact(n-1)，只有n=1时需要特殊处理。
于是，fact(n)用递归的方式写出来就是：

def fact(n):
if n==1:
　　return 1
return n * fact(n - 1)

如果要计算2的n次方，那就是：

def fact(n):
if n==1:
　　return 1
return 2 * fact(n - 1)

我们可以修改一下代码，详细的列出每一步(注意打印出来的内容的顺序哦）：

def fact(n):
    print("factorial has been called with n = " + str(n))
    if n == 1:
        return 1
    else:
        res = n * fact(n - 1)
        print("intermediate result for ", n, " * fact(", n - 1, "): ", res)
        return res


print(fact(10))

结果是：

C:Python35python.exe C:/pylearn/bottlelearn/4.py
factorial has been called with n = 10
factorial has been called with n = 9
factorial has been called with n = 8
factorial has been called with n = 7
factorial has been called with n = 6
factorial has been called with n = 5
factorial has been called with n = 4
factorial has been called with n = 3
factorial has been called with n = 2
factorial has been called with n = 1
intermediate result for  2  * fact( 1 ):  2
intermediate result for  3  * fact( 2 ):  6
intermediate result for  4  * fact( 3 ):  24
intermediate result for  5  * fact( 4 ):  120
intermediate result for  6  * fact( 5 ):  720
intermediate result for  7  * fact( 6 ):  5040
intermediate result for  8  * fact( 7 ):  40320
intermediate result for  9  * fact( 8 ):  362880
intermediate result for  10  * fact( 9 ):  3628800
1814400000

Process finished with exit code 0

进一步思考，如果，我们想实现递归的效果，但是，却不想用到递归，在python怎么实现呢：

def fact(n):
    result=1
    for i in range(2,n+1):
        result=result*i
    return result

print(fact(1))
print(fact(2))
print(fact(10))