3.递归及相关《零基础入门学习python》课22递归

1.例子：

def recursion():
 return recursion()

>>> recursion()
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    recursion()
  File "<pyshell#2>", line 2, in recursion
    return recursion()

RecursionError: maximum recursion depth exceeded（报错，超过了python规定递归的最大深度，默认100层）

2.设置递归层数的方法：

import sys
>>> sys.setrecursionlimit(2400)          #设置递归层数2400

3.递归求阶乘：写一个求阶乘的函数，正整数阶乘指从1乘以2乘以3乘以4一直乘到所要求的数，例如5的阶乘就是1乘以2乘以3乘以4乘以5等于120

写一个非递归版本的阶乘！

def factorial(n):
    result = n                        #result的初始值=n
    for i in range(1,n):           #for语句，范围在1到n-1
        result *= i

    return result

factorial(4)                          #调用函数
24
>>> factorial(5)
120
>>> factorial(1)
1

4.写一个递归版本的阶乘！

def factorial(n):
    if n == 1:                                      #当n=1时，递归结束
        return 1
    else:
        return n * factorial(n-1)             #调用自身函数

5.详细的原理：假设传入值n=5

factorial(5) = 5 * factorial(4)

   factorial(4) = 4 * factorial(3)

      factorial(3) = 3 * factorial(2)

         factorial(2) = 2 * factorial(1)

            factorial(1) = 1   (return)

6.递归的条件：递归表达式（函数调用自身）、递归出口（设置了正确的返回条件）

7.递归在编程上的表现形式：函数调用自身的行为。

8.用递归去计算阶乘问题或斐波那契数列是很糟糕的：因为递归的实现可以是函数调用自身，每次函数的调用都要进行压栈、弹栈、保存和恢复寄存器的栈操作，在这里非常消耗时间和空间，另外如果递归忘记设置返回或错误的设置了返回那么递归代码就会变成一个无底洞出现错误。

9.递归的优点：1.递归的基本思想是把规模大的问题转变成规模小的问题组合，从而简化问题的解决难度。2.有些问题使用递归使得代码简洁易懂。递归的缺点：1.递归层深有限，当大量调用函数自身的时候消耗空间和时间。2.初学者容易错误的设置返回条件，导致递归代码无休止调用，最终栈溢出，程序崩溃

10.使用递归编写一个power()函数模拟内建pow()，即power()为计算并返回x的y次幂的值。
def power(x,y):
    if y:
 return x * power(x,y-1)
    else:
 return 1

11.使用递归编写一个函数，利用欧几里得算法求最大公约数，例如gcd(x,y)返回值为参数x和参数y的最大公约数。
def gcd(x,y):
    if y:
 return gcd(y,x%y)
    else:
 return x