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:\Python35\python.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))