递归函数

递归函数
    定义一个函数后，在此函数内调用自己
    递归函数必须要有结束，否则会一直循环下去,直到栈溢出
    递归函数的执行过程是一层层向内执行到最里层，再一层层向外执行

递归函数的缺点
    递归函数的效率并不高，性能浪费比较大，多数需求也能由for循环完成，所以能不用的情况尽量不要使用

---

# 递归函数
def recursion(n) :
    print('●  '*n)

    if n > 1 :
        recursion(n-1)

    print('●  '*n)

recursion(7)

●  ●  ●  ●  ●  ●  ●  
●  ●  ●  ●  ●  ●  
●  ●  ●  ●  ●  
●  ●  ●  ●  
●  ●  ●  
●  ●  
●  
●  
●  ●  
●  ●  ●  
●  ●  ●  ●  
●  ●  ●  ●  ●  
●  ●  ●  ●  ●  ●  
●  ●  ●  ●  ●  ●  ●  

实现阶乘 方法一：计算过程在函数从内向外执行时，计算顺序是把数字从小到大相乘

def factorial1(n) :

    if n >=3 :
        factorial1(n-1)

    if n == 2 :
        p = 1
    else :
        global m
        p = m

    p = p * n
    m = p
    print(p)

factorial1(7)

2
6
24
120
720
5040

实现阶乘 方法二：计算过程在程序从外向内执行时，计算顺序是把数字从大到小相乘

p = 1
def factorial2(n) :
    global p
    p = p * n

    if n >= 3 :
        factorial2(n-1)

    if n == 2 :
        print(p)

factorial2(5)

120

实现阶乘 方法三

def factorial3(n) :
    if n == 1 :
        return 1
    else :
        return n*factorial3(n-1)

res = factorial3(6)
print(res)

720
6*F5
        5*F4
                4*F3
                        3*F2
                                2*F1
                                        return 1
                                2*1 =2
                        3*2 =6
                4*6 =24
        5*24 =120
6*120 =720

实现斐波那契数列

求第n位的值,1,1,2,3,5,8,13,21,34,55......

方法一

def Fibonacci(n) :
    if n == 1 or n == 2 :
        return 1
    else :
        return Fibonacci(n-1)+Fibonacci(n-2)

res = Fibonacci(5)
print(res)

5
F6+F5   F7
    F5+F4 F4+F3     F6+F5
                F4+F3 F3+F2 F3+F2 F2+F1     F5+F4 + F4+F3
                                        F3+F2 F2+F1 F2+F1 1 F2+F1 1 1+1     4
                                                                        F2+F1 1 2 2 1 2 1 2     3
                                                                                            2 1 2 2 1 2 1 2     2

方法二

需要获取第X位，则发生了X-2次计算，所以用X控制计算次数，X每减少1，计算次数增加1，直至X减少到X=3时，计算完成

n1 = 0
n2 = 1
def fibonacci1(i) :
    global n1,n2

    if i == 1 :
        print(n1)
    elif i == 2 :
        print(n2)

    n = n1 + n2    # 1 2 3
    n1 = n2        # 1 1 2
    n2 = n         # 1 2 3

    if i > 3 :
        fibonacci1(i-1)
    elif i == 3 :
        print(n)
fibonacci1(7)

8