بازگشت به ساده‌ترین مسئله‌ی پیچیده: نگاهی عمیق به Fibonacci و دو مسیر نوشتن آن در Rust و Python

چرا هنوز در سال ۲۰۲۵ داریم به Fibonacci نگاه می‌کنیم؟

گاهی بعضی مسئله‌ها آن‌قدر در برنامه‌نویسی تکرار می‌شوند که تبدیل می‌شوند به یک جور آینه؛ آینه‌ای که مهارت، صبر، و حتی نگاه فلسفی ما را نسبت به ساختارها نشان می‌دهد. دنباله‌ی Fibonacci یکی از همان آینه‌هاست.
یک سری عدد ساده:
۰، ۱، ۱، ۲، ۳، ۵، ۸، ۱۳…

ساده، اما نه بی‌معنا.
در واقع، Fibonacci یک تمرین نیست؛ یک نقطه‌ی برخورد است میان «سادگی» و «پیچیدگی»، میان «بازگشت» و «بهینه‌سازی»، میان «قدرت خام» و «هوشمندی ساختار».

اگر بخواهیم صادق باشیم، هیچ‌کس برای محاسبه‌ی عدد ۱۵۰ام دنباله‌ی Fibonacci از روش ساده‌ی بازگشتی استفاده نمی‌کند. اما همه‌ی ما آن را یک بار می‌نویسیم، فقط برای اینکه با چهره‌ی واقعی پیچیدگی زمانی روبه‌رو شویم؛ همان جایی که ماشین، سکوت نمی‌کند و پردازنده با ناله کار می‌کند.

و همین تجربه است که ما را وادار می‌کند به سمت روش‌های هوشمندتر برویم.
اما قبل از آن، باید از مرحله‌ی ابتدایی عبور کنیم: روشی که درست کار می‌کند، اما اشتباه طراحی شده.

مسیر ساده: بازگشت خام و زیبا، اما کند

نسخه‌ی ساده‌ی Fibonacci شبیه یک شعر است. دو خط if، و سپس یک پرش بازگشتی.
عجیب ساده، عجیب انسانی، و عجیب غیرعملی.

در Rust این‌طور نوشته می‌شود:

fn fib(num: i32) -> i128 {
    if num <= 0 {return 0} 
    else if num == 1 {return 1}

    fib(num -1) + fib(num-2)
}

fn main() {
    let num = 150;
    println!("fib number of {} is {}", num, fib(num));
}

و در Python هم به همین اندازه خام است:

def fib(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    return fib(n-1) + fib(n-2)

print(fib(150))

این نسخه کند است. نه کُندی معمولی… کُندی از جنس رشد نمایی؛ همان O(2ⁿ) که در مصاحبه‌ها از آن می‌ترسیم. چرا؟ چون برای محاسبه‌ی fib(150)، هزاران بار fib(149) و fib(148) دوباره محاسبه می‌شود. هیچ حافظه‌ای ندارد، هیچ نگاه بلندمدتی هم نه. هر بار انگار از صفر شروع می‌کند؛ شبیه آدمی که هر صبح گذشته‌اش را فراموش کرده باشد.

اما این نسخه یک نکته‌ی مهم دارد: این نسخه «ذات» مسئله را فاش می‌کند. می‌فهمیم چرا recursion می‌تواند خطرناک باشد، چرا memoization به وجود آمده، و چرا برنامه‌نویسی فقط «نوشتن کد» نیست.

برای فهمیدن کار درست، باید اول اشتباه را کامل تجربه کنیم.

مسیر سخت: memoization و تبدیل یک ایده‌ی ساده به یک الگوریتم واقعی

برنامه‌نویس حرفه‌ای همیشه یک چیز اضافه دارد: حافظه. نه به معنای ذهنی؛ به معنای اینکه اجازه نمی‌دهد کامپیوتر بی‌هدف محاسبات تکراری انجام دهد.

اینجا memoization وارد صحنه می‌شود. ایده‌اش ساده است: «وقتی یک جواب را یک بار حساب کردی، نگهش دار.»

در نسخه‌ی بهینه‌ی Rust، از HashMap استفاده می‌کنیم تا نتیجه‌های قبلی ذخیره شوند:

use std::collections::HashMap;

fn fib(num: i32) -> i128 {
    if num <= 0 {return 0} 
    else if num == 1 {return 1}

    let mut m = HashMap::new();
    rec_fib(num -1, &mut m) + rec_fib(num-2, &mut m)
}

fn rec_fib(num: i32, memo: &mut HashMap<i32, i128>) -> i128 {
    if num <= 0 {return 0} 
    else if num == 1 {return 1}

    if let Some(&val) = memo.get(&num) {
        return val;
    }

    let val = rec_fib(num -1, memo) + rec_fib(num-2, memo);
    memo.insert(num, val);
    val
}

fn main() {
    let num = 150;
    println!("fib number of {} is {}", num, fib(num));
}

و یا اگر حتما بخواهیم که همه ی منطق را فقط در یک تابع جا بدیم:

use std::collections::HashMap;

fn fib(num: i32) -> i128 {
    if num <= 0 {return 0} 
    else if num == 1 {return 1}

    let mut m = HashMap::new();
    rec_fib(num -1, &mut m) + rec_fib(num-2, &mut m)
}

fn rec_fib(num: i32, memo: &mut HashMap<i32, i128>) -> i128 {
    if num <= 0 {return 0} 
    else if num == 1 {return 1}

    if let Some(&val) = memo.get(&num) {
        return val;
    }

    let val = rec_fib(num -1, memo) + rec_fib(num-2, memo);
    memo.insert(num, val);
    val
}

fn main() {
    let num = 150;
    println!("fib number of {} is {}", num, fib(num));
}

در Python نیز همین الگو وجود دارد:

memo = {}

def fib(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1

    if n in memo:
        return memo[n]

    value = fib(n-1) + fib(n-2)
    memo[n] = value
    return value

print(fib(150))

این‌جا اتفاق مهمی می‌افتد: پیچیدگی زمانی از O(2ⁿ) به O(n) سقوط می‌کند. این یعنی از یک مسیر پر از تکرار بیهوده، می‌رسی به یک مسیر مستقیم و هدفمند.

و این، همان نقطه‌ای است که recursion از «خطرناک» تبدیل می‌شود به «زیبا».

در حقیقت، برنامه‌نویسان سال‌هاست به این نتیجه رسیده‌اند که recursion بدون memoization مثل نوشتن جمله‌ای زیبا روی شن است: موج بعدی دوباره از نو مجبور می‌کند بنویسی.

وقتی memoization اضافه می‌شود، مسئله بالاخره معنی پیدا می‌کند: این بار حافظه کنار توست؛ این بار سیستم بالاخره می‌فهمد که قرار نیست گذشته‌اش را فراموش کند.

سخن آخر — الگوریتم، فقط کد نیست

در نگاه سطحی، Fibonacci یک تمرین ساده است. اما وقتی کمی عمیق‌تر می‌شوی، می‌بینی که مسئله‌ای کوچک چگونه تبدیل می‌شود به تلاقی مفاهیمی مثل:

• رشد نمایی
• حافظه
• بازگشت
• ساختار
• و حتی رابطه‌ی انسان با پیچیدگی

یک الگوریتم کوچک، یک جهان کوچک است. و شاید دلیل اینکه Fibonacci این‌قدر جاودانه شده، همین است: ساده شروع می‌شود، اما تو را مجبور می‌کند واقعاً درباره‌ی «فکر کردن» فکر کنی.

اگر تمام قدرت پردازنده را به ساده‌ترین روش می‌سوزانی، یا اگر با کمی حافظه مسیر را هزار برابر کوتاه‌تر می‌کنی… در هر دو حالت داری همان چیزی را تمرین می‌کنی که جوهره‌ی برنامه‌نویسی است: انتخاب.

و Fibonacci فقط بهانه‌ای است برای تمرین این انتخاب.