# Python递归教程实例操作

XAMPP案例 878浏览

``````movies = ["The Holy Grail", 1975, "Terry Jones & Terry Gilliam", 91,
``````          ["Graham Chapman", ["Michael Palin", "John Cleese",
````                              "Terry Gilliam", "Eric Idle", "Terry Jones"]]]````

``````movies = ["The Holy Grail", 1975, "Terry Jones & Terry Gilliam", 91,
``````          ["Graham Chapman", ["Michael Palin", "John Cleese",
``````                              "Terry Gilliam", "Eric Idle", "Terry Jones"]]]
``````
``````for each_item in movies:
``````    if isinstance(each_item, list):
``````        for nested_item in each_item:
``````            if isinstance(nested_item, list):
``````                for deeper_item in nested_item:
``````                    print(deeper_item)
``````            else:
``````                print(nested_item)
``````    else:
````        print(each_item)````

``````def print_item(items):
``````    for item in items:
``````        if isinstance(item, list):
``````            print_item(item)
``````        else:
``````            print(item)
``````
``````
``````movies = ["The Holy Grail", 1975, "Terry Jones & Terry Gilliam", 91,
``````          ["Graham Chapman", ["Michael Palin", "John Cleese",
``````                              "Terry Gilliam", "Eric Idle", "Terry Jones"]]]
````print_item(movies)````

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

2. 每次进入更深一层递归时，问题规模（计算量）相比上一次递归都会有所减少

3. 递归效率不高，递归层次过多会导致栈溢出

N! = 1 * 2 * 3 * … * N = factorial(N)

factorial(N) = N!

= N * (N-1)!

= N * (N-1) * (N-2)!

= N * (N-1) * (N-2) … * 3 * 2 * 1

``````def factorial(n):
``````    """递归"""
``````    if n == 1:
``````        return 1
``````    else:
``````        return n * factorial(n-1)
``````
``````
````print(factorial(5))````

``````===> factorial(5)
``````递的过程：
``````===> n=5, retrun n * factorial(n-1)  ==>  5 * factorial(4)
``````===> n=4, retrun n * factorial(n-1)  ==>  4 * factorial(3)
``````===> n=3, retrun n * factorial(n-1)  ==>  3 * factorial(2)
``````===> n=2, retrun n * factorial(n-1)  ==>  2 * factorial(1)
``````===> n=1, retrun 1
``````归的过程：
``````===> n=2, retrun 2 * factorial(2-1)  ==>  2 * 1 = 2
``````===> n=3, retrun 3 * factorial(2)  ==>  3 * 2 = 6
``````===> n=4, retrun n * factorial(n-1)  ==>  4 * 6 = 24
````===> n=5, retrun 5 * factorial(5-1)  ==>  5 * 24 = 120````

``````def factorial(n):
``````    result = 1
``````    for i in range(1, n+1):
``````        result *= i
``````    return result
``````
``````
````print(factorial(5))````

``````def factorial(n):
``````    """优化"""
``````    return fact_iter(n, 1)
``````
``````
``````def fact_iter(num, result):
``````    if num == 1:
``````        return result
``````    return fact_iter(num-1, num*result)
``````
``````
````print(factorial(5))````

fact(5)对应的fact_iter(5, 1)的调用如下：

``````===> fact_iter(5, 1)
``````===> fact_iter(4, 5)
``````===> fact_iter(3, 20)
``````===> fact_iter(2, 60)
``````===> fact_iter(1, 120)
````===> 120````

Tips：注意调用函数本身的时候，下面的代码只是被暂停了哦~

``````def test(n):
``````    """递归练习"""
``````    print(n)
``````    if n > 0:
``````        test(n-1)
``````    else:
``````        print("-"*5)
``````    print(n)
``````
``````
````print(test(3))````