পাইথন প্রোগ্রাম: রিকার্শন ব্যবহার করে ফিবোনাচি সিকোয়েন্স প্রিন্ট করা

ভূমিকা

ফিবোনাচি সিকোয়েন্স (Fibonacci sequence) হলো একটি বিখ্যাত সংখ্যা সিরিজ যেখানে প্রতিটি সংখ্যা পূর্বের দুটি সংখ্যার যোগফল (0, 1, 1, 2, 3, 5, 8, 13, ...)। রিকার্শন (recursion) ব্যবহার করে এটি জেনারেট করা একটি ক্লাসিক প্রোগ্রামিং উদাহরণ, যদিও বড় ইনপুটের জন্য এটি অপ্টিমাইজড নয়।

উদাহরণ কোড

def fibonacci_recursion(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursion(n-1) + fibonacci_recursion(n-2)

num_terms = 12
if num_terms <= 0:
    print("Enter a positive integer")
else:
    print("The fibonacci sequence is :")
    for i in range(num_terms):
        print(fibonacci_recursion(i))

আউটপুট

The fibonacci sequence is :
0
1
1
2
3
5
8
13
21
34
55
89

ব্যাখ্যা

• fibonacci_recursion(n) ফাংশনটি বেস কেস: n <= 1 হলে n রিটার্ন করে (0 বা 1)।

• রিকার্সিভ কেস: fib(n-1) + fib(n-2) কল করে।

• লুপে range(num_terms) দিয়ে ০ থেকে ১১ পর্যন্ত ফিবোনাচি সংখ্যা প্রিন্ট করা হয়েছে।

পারফরম্যান্স নোট

এই রিকার্সিভ অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(2^n) (এক্সপোনেনশিয়াল), কারণ একই সাব-প্রব্লেম বারবার সমাধান করা হয়। বড় n (যেমন ৪০+) এর জন্য এটি খুব ধীর হবে।

উন্নত সমাধান: মেমোইজেশন (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)

# অথবা ইটারেটিভ পদ্ধতি (O(n) টাইম, O(1) স্পেস)
def fib_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

প্রোডাকশন কোডে রিকার্শনের বদলে ইটারেটিভ বা মেমোইজড ভার্শন ব্যবহার করুন।