中文字幕av专区_日韩电影在线播放_精品国产精品久久一区免费式_av在线免费观看网站

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

高階函數-遞歸

發布時間:2020-08-06 03:28:42 來源:網絡 閱讀:414 作者:DevOperater 欄目:編程語言

1.高階函數

1.1高階函數定義

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

#!/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遞歸定義

在函數內部,可以調用其它函數。如果一個函數在內部調用自身,這個函數就是遞歸函數。

#!/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遞歸的執行過程

#!/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.必須有一個明確的結束條件
2.每次進入更深一層遞歸時,問題規模相比上次遞歸都應有所減少
3.遞歸效率不高,遞歸層次過多會導致棧溢出(在計算機中,函數調用時通過棧(stack)這種數據結構實現的,每當進入一個函數調用,棧就會加一層棧幀,每當函數返回,棧就會減一層棧幀。由于棧的大小不是無限的,所以遞歸調用的次數過多,會導致棧溢出)

    #!/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尾遞歸

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

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

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

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

python中實際是沒有做尾遞歸的優化,但別的語言有優化的

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

个旧市| 青海省| 友谊县| 丹凤县| 漳州市| 龙井市| 囊谦县| 青川县| 长泰县| 图片| 合山市| 长海县| 刚察县| 石狮市| 达拉特旗| 新竹市| 永清县| 弥渡县| 射阳县| 尼勒克县| 扎兰屯市| 新野县| 夏河县| 丽江市| 海城市| 津南区| 车致| 灵丘县| 隆化县| 巴林右旗| 固安县| 神池县| 荔波县| 大丰市| 溧阳市| 桦甸市| 黎城县| 伽师县| 聊城市| 天峻县| 察隅县|