โปรแกรม Python แสดงลำดับฟีโบนัชชีด้วย Recursion

ภาพรวม

สร้างลำดับฟีโบนัชชี (Fibonacci sequence) โดยใช้ฟังก์ชันเรียกซ้ำ (recursion)

ตัวอย่างโค้ด

def fibonacci_recursion(n):
    """ส่งคืนเลขฟีโบนัชชีตัวที่ n"""
    if n <= 1:
        return n
    else:
        return fibonacci_recursion(n-1) + fibonacci_recursion(n-2)

num_terms = 12

if num_terms <= 0:
    print("กรุณาใส่จำนวนเต็มบวก")
else:
    print("ลำดับฟีโบนัชชี:")
    for i in range(num_terms):
        print(fibonacci_recursion(i), end=" ")

ผลลัพธ์

ลำดับฟีโบนัชชี:
0 1 1 2 3 5 8 13 21 34 55 89

คำอธิบาย

• Base case: n=0 คืน 0, n=1 คืน 1
• Recursive case: F(n) = F(n-1) + F(n-2)
• ลูปเรียกฟังก์ชันสำหรับ i = 0 ถึง num_terms-1

ข้อควรระวัง

วิธี recursion แบบนี้มี time complexity เป็น O(2^n) เหมาะสำหรับ n เล็ก (n < 35) สำหรับค่ามากควรใช้ dynamic programming หรือ iterative approach

เวอร์ชันที่มีประสิทธิภาพมากกว่า (Memoization)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n-1) + fib_memo(n-2)