درس ۴ سطح متوسط: الگوریتم‌های بازگشتی (Recursion) و پیشرفته در پایتون

سلام قهرمان واقعی پایتون! تبریک می‌گم که تا درس چهارم سطح متوسط رسیدی. الان دیگه واقعاً داری وارد قلمرو برنامه‌نویس‌های حرفه‌ای می‌شی. تو این درس قراره یه مهارت جادویی و فوق‌العاده قدرتمند رو یاد بگیری که خیلی از برنامه‌نویس‌ها سال‌ها طول می‌کشه تا درست بفهمنش: الگوریتم‌های بازگشتی یا به انگلیسی Recursion. وقتی این درس تموم بشه، تو می‌تونی مسائلی رو حل کنی که با حلقه‌های معمولی یا خیلی پیچیده می‌شن یا حتی غیرممکن. این همون چیزیه که شرکت‌های بزرگ مثل گوگل، مایکروسافت و متا توی مصاحبه‌هاشون ازت می‌خوان! اگه درس‌های قبلی (مخصوصاً توابع، لیست‌ها و شیءگرایی) رو خوب بلدی، الان بهترین زمانه که ذهنت رو به چالش بکشی و یه سطح کاملاً جدید از تفکر الگوریتمی رو تجربه کنی. آماده‌ای؟ بریم که مغزت رو روشن کنیم!

بازگشتی یعنی چی؟ یه مثال ساده و جادویی

فرض کن می‌خوای فاکتوریل یه عدد رو حساب کنی. راه معمولیش اینه که با حلقه for ضرب کنی. اما راه بازگشتی چطوریه؟ تابع خودش رو صدا می‌زنه! دقیقاً مثل وقتی که توی آینه به آینه نگاه می‌کنی و بی‌نهایت تصویر می‌بینی.

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

print(factorial(5))  # خروجی: ۱۲۰

این تابع خودش رو صدا می‌زنه تا وقتی به شرط پایه (base case) برسه. بدون شرط پایه، برنامه بی‌نهایت اجرا می‌شه و کرش می‌کنه!

چرا الگوریتم بازگشتی پایتون اینقدر مهمه؟

بعضی مسائل ذاتاً بازگشتی هستن. مثلاً:

• پیمایش درخت‌ها و گراف‌ها
• الگوریتم‌های مرتب‌سازی پیشرفته (Quick Sort, Merge Sort)
• مسائل معروف مثل برج هانوی، فیبوناچی، زیرمجموعه‌ها
• برنامه‌نویسی تابعی و هوش مصنوعی

مثال‌های واقعی و خفن

۱. سری فیبوناچی با بازگشتی

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

for i in range(10):
    print(fib(i), end=" ")  # 0 1 1 2 3 5 8 13 21 34

۲. جمع ارقام یک عدد

def sum_digits(n):
    if n < 10:
        return n
    return n % 10 + sum_digits(n // 10)

print(sum_digits(687))  # 6+8+7 = 21

۳. معکوس کردن رشته

def reverse_string(s):
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]

print(reverse_string("سلام پایتون"))

۴. برج هانوی – مسئله کلاسیک مصاحبه

def hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"دیسک ۱ از {source} به {target}")
        return
    hanoi(n-1, source, target, auxiliary)
    print(f"دیسک {n} از {source} به {target}")
    hanoi(n-1, auxiliary, source, target)

hanoi(3, 'A', 'B', 'C')

بازگشتی vs حلقه – کی از کدوم استفاده کنیم؟

بازگشتی دم (Tail Recursion) و بهینه‌سازی

پایتون بهینه‌سازی Tail Recursion رو انجام نمی‌ده (برخلاف بعضی زبان‌ها)، اما می‌تونی خودت با حلقه شبیه‌سازی کنی یا از کتابخانه‌های خاص استفاده کنی.

ترکیب بازگشتی با شیءگرایی و pandas

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
    
    def add_child(self, child_node):
        self.children.append(child_node)
    
    def print_tree(self, level=0):
        print("  " * level + str(self.value))
        for child in self.children:
            child.print_tree(level + 1)

# ساخت درخت
root = TreeNode("ریشه")
child1 = TreeNode("فرزند ۱")
child2 = TreeNode("فرزند ۲")
root.add_child(child1)
root.add_child(child2)
child1.add_child(TreeNode("نوه ۱"))

root.print_tree()

۱۲ تمرین آتشین برای تسلط کامل روی الگوریتم بازگشتی پایتون

1. فاکتوریل با حلقه و بازگشتی بنویس و زمان اجرا رو مقایسه کن
2. توان یک عدد (مثل ۲^۱۰) رو با توابع بازگشتی پایتون حساب کن
3. بزرگ‌ترین عدد در یک لیست رو با بازگشتی پیدا کن
4. طول یک لیست رو بدون len() و با بازگشتی حساب کن
5. همه زیررشته‌های یک رشته رو چاپ کن (Power Set)
6. برج هانوی با ۴ دیسک حل کن
7. تعداد راه‌های رفتن از (۰,۰) به (m,n) در یک گرید (فقط راست و پایین)
8. همه ترتیب‌های ممکن حروف یک کلمه رو چاپ کن (Permutation)
9. یه تابع بازگشتی بنویس که بگه یک عدد پالین‌دروم هست یا نه
10. یه درخت باینری جستجو بساز و با بازگشتی پیمایش کن (In-order)
11. الگوریتم Quick Sort رو با بازگشتی پیاده کن
12. کلاس کامل File Explorer بساز که ساختار پوشه‌ها رو بازگشتی نمایش بده

پروژه نهایی درس: حل‌کننده کامل مسائل بازگشتی

class RecursionMaster:
    def factorial(self, n):
        if n <= 1: return 1
        return n * self.factorial(n-1)
    
    def fibonacci(self, n, memo={}):
        if n in memo: return memo[n]
        if n <= 1: return n
        memo[n] = self.fibonacci(n-1, memo) + self.fibonacci(n-2, memo)
        return memo[n]
    
    def power(self, base, exp):
        if exp == 0: return 1
        if exp == 1: return base
        return base * self.power(base, exp-1)
    
    def gcd(self, a, b):
        if b == 0: return a
        return self.gcd(b, a % b)  # الگوریتم اقلیدس بازگشتی

master = RecursionMaster()
print("فاکتوریل ۷:", master.factorial(7))
print("فیبوناچی ۱۰:", master.fibonacci(10))
print("ب.م.م ۴۸ و ۱۸:", master.gcd(48, 18))

جمع‌بندی و قدم بعدی

تبریک می‌گم! تو الان رسماً یه برنامه‌نویس حرفه‌ای شدی که بازگشتی رو نه فقط بلده، بلکه عاشقش هم هست. این مهارت توی مصاحبه‌های شغلی، پروژه‌های پیچیده و حتی المپیاد برنامه‌نویسی برات درخشش میاره. درس بعدی قراره درباره ساختارهای داده پیشرفته (Heap, Graph, Trie) باشه. تمرین‌ها رو انجام بده، پروژه رو توی GitHub آپلود کن و منتظر درس بعدی باش. تو داری به قله نزدیک می‌شی!