1. 遞歸

1.1 定義

函數(shù)作為一種代碼封裝， 可以被其他程序調(diào)用，當然，也可以被函數(shù)內(nèi)部代碼調(diào)用。這種函數(shù)定義中調(diào)用函數(shù)自身的方式稱為遞歸。就像一個人站在裝滿鏡子的房間中，看到的影像就是遞歸的結果。遞歸在數(shù)學和計算機應用上非常強大，能夠非常簡潔地解決重要問題。

數(shù)學上有個經(jīng)典的遞歸例子叫階乘，階乘通常定義如下:

n!= n(n- 1)(n- 2)…(1)

為了實現(xiàn)這個程序，可以通過一個簡單的循環(huán)累積去計算階乘。觀察 5! 的計算，如果去掉了 5，那么就剩下計算 4!，推廣來看，n!=n(n-1)!。 實際上，這個關系給出了另一種表達階乘的方式：

當 n = 0 時，n! = 1；否則，n! = n(n - 1)!

這個定義說明 0 的階乘按定義是 1，其他數(shù)字的階乘定義為這個數(shù)字乘以比這個數(shù)字小 1 數(shù)的階乘。遞歸不是循環(huán)，因為每次遞歸都會計算比它更小數(shù)的階乘，直到 0!。0! 是已知的值，被稱為遞歸的基例。當遞歸到底了，就需要一個能直接算出值的表達式。

階乘的例子揭示了遞歸的兩個關鍵特征：

(1) 存在一個或多個基例，基例不需要再次遞歸，它是確定的表達式。

(2) 所有遞歸鏈要以一個或多個基例結尾。

1.2 數(shù)學歸納法

數(shù)學歸納法和遞歸都利用了遞推原理，本質(zhì)是相同的。在證明一個與自然數(shù)相關的命題 P(n) 時，數(shù)學歸納法采用如下步驟。

(1) 證明當 n 取第一個值 n0 時命題成立。

(2) 假設當 nk ( k ≥ 0, k 為自然數(shù) ) 時命題成立，證明當 n=nk+1 時命題也成立。

綜合 (1) 和 (2)，對一切自然數(shù) n( n ≥ n0)，命題 P(n) 都成立。

2. 遞歸的使用方法

2.1 階乘

以階乘計算為例，可以把階乘寫成一個單獨的函數(shù)，則該函數(shù)如下所示：

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

num = eval(input("請輸入一個整數(shù)："))
print(fact(abs(int(num))))

fact() 函數(shù)在其定義內(nèi)部引用了自身，形成了遞歸過程(如第 5 行)。無限制的遞歸將耗盡計算資源，因此，需要設計基例使得遞歸逐層返回。fact() 函數(shù)通過 if 語句給出了 n 為 0 時的基例，當 n==0，fact() 函數(shù)不再遞歸， 返回數(shù)值 1，如果 n!=0，則通過遞歸返回 n 與 n-1 階乘的乘積。

由于負數(shù)和小數(shù)通過減 1 無法到達遞歸的基例 (n==0)， 代碼第 8 行通過 abs() 和 int() 函數(shù)將用戶輸入轉(zhuǎn)變成非負整數(shù)，該程序輸出效果如下:

請輸入一個整數(shù)：5

120

請輸入一個整數(shù)：6.789

720

遞歸遵循函數(shù)的語義，每次調(diào)用都會引起新函數(shù)的開始，表示它有本地變量值的副本，包括函數(shù)的參數(shù)。每次函數(shù)調(diào)用時，函數(shù)參數(shù)的副本會臨時存儲，遞歸中各函數(shù)再運算自己的參數(shù)，相互沒有影響。當基例結束運算并返回值時，各函數(shù)逐層結束運算，向調(diào)用者返回計算結果。

使用遞歸一定要注意基例的構建，否則遞歸無法返回將會報錯。

2.2 字符串反轉(zhuǎn)

對于用戶輸入的字符串 s，輸出反轉(zhuǎn)后的字符串。

解決這個問題的基本思想是把字符串看作一個遞歸對象。長字符串由較短字符串組成，每個小字符串也是一個對象。假如把一個字符串看成僅由兩部分組成：首字符和剩余字符串。如果將剩余字符串與首字符交換，就完成了反轉(zhuǎn)整個字符串，代碼如下：

def reverse(s):
    return reverse((s[1:]) + s[0])

觀察這個函數(shù)的工作過程。s[0] 是首字符，s[1:] 是剩余字符串，將它們反向連接，可以得到反轉(zhuǎn)字符串。執(zhí)行這個程序，結果如下:

def reverse(s):
    return reverse(s[1:]) + s[0]
reverse("abc")

return reverse(s[1:]) + s[0]
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

這個錯誤表明系統(tǒng)無法執(zhí)行 reverse() 函數(shù)創(chuàng)建的遞歸，這是因為 reverse() 函數(shù)沒有基例，遞歸層數(shù)超過了系統(tǒng)允許的最大遞歸深度。默認情況下，當遞歸調(diào)用到 1000 層，Python 解釋器將終止程序。遞歸深度是為了防止無限遞歸錯誤而設計的，當用戶編寫的正確遞歸程序需要超過 1000 層時，可以通過如下代碼設定：

import sys
sys.setrecursionlimit(2000)    # 2000 是新的遞歸層數(shù)

reverse() 超過遞歸深度是因為沒有設計基例。字符串反轉(zhuǎn)中的遞歸調(diào)用總是使用比之前更短的字符串，因此，可以把基例設計為字符串的最短形式，即空字符串。

完整代碼如下：

def reverse(s):
    if s == "":
        return s
    else:
        return reverse(s[1:]) + s[0]

str = input("請輸入一個字符串：")
print(reverse(str))

程序執(zhí)行結果如下：

請輸入一個字符串：Python程序設計
計設序程nohtyP

3. 科赫曲線的繪制

3.1 概要

這是一個采用遞歸方法繪制科赫曲線的實例，分形幾何采用類似遞歸的核心思想。

自然界有很多圖形很規(guī)則，符合一定的數(shù)學規(guī)律， 例如，蜜蜂的蜂窩是天然的等邊六角形等?？坪涨€在眾多經(jīng)典數(shù)學曲線中非常著名，由瑞典數(shù)學家馮?？坪? H-V-Koch )于 1904 年提出，由于其形狀類似雪花，也被稱為雪花曲線。

科赫曲線的基本概念和繪制方法如下：

正整數(shù) n 代表科赫曲線的階數(shù)，表示生成科赫曲線過程的操作次數(shù)。科赫曲線初始化階數(shù)為 0，表示一個長度為 L 的直線。對于直線 L，將其等分為 3 段，中間一段用邊長為 L/3 的等邊三角形的兩個邊替代，得到 1 階科赫曲線，它包含 4 條線段。進一步對每條線段重復同樣的操作后得到 2 階科赫曲線。繼續(xù)重復同樣的操作 n 次可以得到 n 階科赫曲線，如下圖所示：

3.2 繪制科赫曲線

科赫曲線屬于分形幾何分支，它的繪制過程體現(xiàn)了遞歸思想，繪制過程代碼如下：

import turtle
def koch(size, n):
    if n == 0:
        turtle.fd(size)
    else:
        for angle in [0, 60, -120, 60]:
            turtle.left(angle)
            koch(size / 3, n - 1)
def main():
    turtle.setup(800, 400)
    turtle.speed(0)  # 控制繪制速度
    turtle.penup()
    turtle.goto(-300, -50)
    turtle.pendown()
    turtle.pensize(2)
    koch(600, 6)  # 0階科赫曲線長度，階數(shù)
    turtle.hideturtle()

main()

程序執(zhí)行結果如下：

n 階科赫曲線的繪制相當于在畫筆前進方向的 0°、60°、-120° 和 60° 分別繪制 n-1 階曲線。上述代碼中 main() 函數(shù)設置了一些初始參數(shù)，如果希望控制繪制科赫曲線的速度，可以采用 turtle.speed() 函數(shù)增加或減少速度。

3.3 科赫曲線的雪花效果

科赫曲線從一條直線繪制開始，如果從倒置的三角形開始將更有趣。替換前面代碼中的 main() 函數(shù)，代碼如下：

import turtle

def koch(size, n):
    if n == 0:
        turtle.fd(size)
    else:
        for angle in [0, 60, -120, 60]:
            turtle.left(angle)
            koch(size / 3, n - 1)

def main():
    turtle.setup(600, 600)
    turtle.speed(1000)
    turtle.penup()
    turtle.goto(-200, 100)
    turtle.pendown()
    turtle.pensize(2)
    level = 5
    koch(400, level)
    turtle.right(120)
    koch(400, level)
    turtle.right(120)
    koch(400, level)
    turtle.hideturtle()

main()

程序執(zhí)行結果如下：

3.4 分形幾何

分形幾何學是數(shù)學的一個分支，以不規(guī)則幾何形態(tài)為研究對象。分形以自相似結構為基礎，通過無限遞歸方式展示復雜表面下的內(nèi)在數(shù)學秩序。分形幾何不僅展示了數(shù)學之美，也揭示了世界的本質(zhì)，使人們重新審視這個世界：世界是非線性的，分形無處不在。

到此這篇關于詳解如何利用Python繪制科赫曲線的文章就介紹到這了,更多相關Python科赫曲線內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論