高階函數(shù)-遞歸

1.高階函數(shù)

1.1高階函數(shù)定義

變量可以指向函數(shù)，函數(shù)的參數(shù)能接受變量，那么一個函數(shù)就可以接收另一個函數(shù)作為參數(shù)，這種函數(shù)就稱為高階函數(shù)。
只要滿足以下任意一個條件，即是高階函數(shù)
1.接收一個或多個函數(shù)作為輸入
2.return返回另外一個函數(shù)

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def add(x, y, func):
    return func(x) + func(y)
res = add(3, -6, abs)
print(res)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
9

Process finished with exit code 0

2.遞歸

2.1遞歸定義

在函數(shù)內(nèi)部，可以調(diào)用其它函數(shù)。如果一個函數(shù)在內(nèi)部調(diào)用自身，這個函數(shù)就是遞歸函數(shù)。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def calc(n):
    print(n)
    if int(n/2) == 0:
        return n
    return calc(int(n/2))
calc(4)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
4
2
1

Process finished with exit code 0

2.2遞歸的執(zhí)行過程

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def calc(n):
    print(n)
    if int(n/2) > 0:
        calc(int(n/2))
    print(n)
calc(4)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
4
2
1
1
2
4

Process finished with exit code 0

2.3遞歸特性

1.必須有一個明確的結(jié)束條件
2.每次進入更深一層遞歸時，問題規(guī)模相比上次遞歸都應(yīng)有所減少
3.遞歸效率不高，遞歸層次過多會導(dǎo)致棧溢出（在計算機中，函數(shù)調(diào)用時通過棧(stack)這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，每當進入一個函數(shù)調(diào)用，棧就會加一層棧幀，每當函數(shù)返回，棧就會減一層棧幀。由于棧的大小不是無限的，所以遞歸調(diào)用的次數(shù)過多，會導(dǎo)致棧溢出）

    #!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def recursion(n):
    print(n)
    recursion(n + 1)

recursion(1)
運行
...
996
997
998
Process finished with exit code 1
"到998程序就自動停止了，是因為遞歸的最大深度是有限制的，防止棧溢出"

2.4二分法查找

    #!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

data = [1, 3, 5, 7, 8, 10, 30, 34, 35]

def binary_search(source_data, search_data):
    print(source_data)
    if len(source_data) > 1:
        mid_data_index = int(len(source_data)/2)
        if source_data[mid_data_index] == search_data:
            print("excellent,you have found it!")
        elif source_data[mid_data_index] > search_data:
            source_data = source_data[0:mid_data_index]
            binary_search(source_data, search_data)
        elif source_data[mid_data_index] < search_data:
            source_data = source_data[mid_data_index + 1:]
            binary_search(source_data, search_data)
    else:
        if len(source_data) == 0:
            print("source data is null now!")
        else:
            if source_data[0] == search_data:
                print("you have found it!")
            else:
                print("there is not this number!")
binary_search(data, 30)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
[1, 3, 5, 7, 8, 10, 30, 34, 35]
[10, 30, 34, 35]
[10, 30]
excellent,you have found it!

Process finished with exit code 0
"找4"
binary_search(data, 4)
E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
[1, 3, 5, 7, 8, 10, 30, 34, 35]
[1, 3, 5, 7]
[1, 3]
[]
source data is null now!

Process finished with exit code 0

2.5求階乘

#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

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

print(multi(4))

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
24

Process finished with exit code 0

2.6斐波那契

    #!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita
# 1 1 2 3 5 8 13
a = 0
b = 1
n = 0
def fibs(a, b):
    global n
    a, b = b, a + b
    print(a)
    if n == 5:
        return
    n += 1
    fibs(a, b)

fibs(a,b)

E:\PythonProject\python-test\venvP3\Scripts\python.exe E:/PythonProject/python-test/BasicGrammer/test.py
1
1
2
3
5
8

Process finished with exit code 0

2.7尾遞歸

再講遞歸特性時，我們說遞歸效率不高，因為每遞歸一次，就多了一層棧，遞歸次數(shù)過多就會棧溢出，這也是Python默認會限制遞歸次數(shù)的原因。但有一種方式是可以在遞歸過程中不產(chǎn)生多層棧，即尾遞歸。
如果一個函數(shù)中所有遞歸形式的調(diào)用都出現(xiàn)在函數(shù)的末尾，我們稱這個遞歸函數(shù)是尾遞歸的。當遞歸調(diào)用時整個函數(shù)體重最后執(zhí)行的語句且它的返回值不屬于表達式的一部分，這個遞歸調(diào)用就是尾遞歸。尾遞歸函數(shù)的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數(shù)現(xiàn)代的編譯機會利用這個特點自動生成優(yōu)化的代碼。
當編譯器檢測到一個函數(shù)調(diào)用時尾遞歸，就會覆蓋當前活動記錄，而不是在棧中去創(chuàng)建新的。編譯器可以做到這點，因為遞歸調(diào)用時當前活躍期內(nèi)最后執(zhí)行的一條語句，于是當這個調(diào)用返回時幀棧中并沒有其他事情可做，因此也就沒有保存棧幀的必要了。通過覆蓋當前的棧幀而不是重新添加一個，這樣就節(jié)省了棧幀的使用，運行效率變高。

"尾遞歸的例子"
#!/usr/bin/env python
# -*- coding:utf-8 -*-
# Author: vita

def calc(n):
    print(n)
    if n > 0:
        return calc(n-1)
calc(8)

那么階乘的例子是尾遞歸嗎？
不是尾遞歸，因為每個活躍的返回值都依賴于用n乘以下一個活躍期的返回值，因此每次調(diào)用產(chǎn)生的棧幀不得不保存在棧上直到下一個子調(diào)用的返回值確定。

python中實際是沒有做尾遞歸的優(yōu)化，但別的語言有優(yōu)化的