تابع بازگشتی در پایتون؛ فاکتوریل، فیبوناچی و RecursionError با مثال

🗓 آخرین به‌روزرسانی: 26 مهر 1405

تابع بازگشتی (Recursive Function) در پایتون تابعی است که برای حل یک مسئله، خودش را صدا می‌زند. شاید در نگاه اول عجیب به نظر برسد که تابعی داخل بدنه خودش دوباره اجرا شود، اما همین ایده ساده پشت بسیاری از الگوریتم‌های مهم است: از محاسبه فاکتوریل و فیبوناچی گرفته تا جستجوی دودویی، پیمایش پوشه‌ها و کار با داده‌های تودرتو مثل JSON. در این آموزش قدم‌به‌قدم یاد می‌گیرید بازگشت در پایتون چطور کار می‌کند، چرا هر تابع بازگشتی به «حالت پایه» نیاز دارد، پشت صحنه پشته فراخوانی چه اتفاقی می‌افتد و چطور از خطای RecursionError جلوگیری کنید. همه کدها روی پایتون ۳.۱۳ اجرا شده‌اند و خروجی واقعی آن‌ها زیر هر کد آمده است.

تابع بازگشتی چیست؟ تعریف ساده

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

یک مثال روزمره: فرض کنید در صف طولانی ایستاده‌اید و می‌خواهید بدانید نفر چندم هستید. از نفر جلویی می‌پرسید «تو نفر چندمی؟» و او همین سؤال را از نفر جلوی خودش می‌پرسد. این زنجیره تا نفر اول ادامه دارد که بدون پرسیدن می‌داند نفر اول است. حالا جواب‌ها به عقب برمی‌گردند و هر کس یک واحد به عدد نفر جلویی اضافه می‌کند. این دقیقاً منطق یک تابع بازگشتی است: یک حالت پایه (نفر اول) و یک گام بازگشتی (پرسیدن از نفر جلویی و اضافه کردن یک).

دو جزء اصلی هر تابع بازگشتی

• حالت پایه (Base Case): شرطی که در آن تابع بدون صدا زدن خودش جواب را برمی‌گرداند. بدون حالت پایه، بازگشت هرگز تمام نمی‌شود.
• گام بازگشتی (Recursive Case): بخشی که تابع خودش را با ورودی کوچک‌تر صدا می‌زند و مسئله را یک قدم به حالت پایه نزدیک‌تر می‌کند.

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

def countdown(n):
    if n == 0:              # base case
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)        # recursive case

countdown(5)

خروجی:

5
4
3
2
1
Liftoff!

همین کار را می‌شد با یک حلقه while هم انجام داد. اما هدف این مثال دیدن ساختار است: یک شرط برای توقف و یک فراخوانی با ورودی کوچک‌تر. هر تابع بازگشتی درستی که می‌نویسید باید همین دو بخش را داشته باشد.

محاسبه فاکتوریل با تابع بازگشتی

فاکتوریل عدد n که با n! نشان داده می‌شود، حاصل‌ضرب همه اعداد از ۱ تا n است؛ مثلاً ۵! برابر ۱۲۰ است. تعریف ریاضی فاکتوریل خودش بازگشتی است: n! برابر است با n ضرب در (n-1)! و فاکتوریل صفر و یک برابر ۱ است. این تعریف تقریباً خط‌به‌خط به کد پایتون تبدیل می‌شود:

def factorial(n):
    if n <= 1:                      # base case
        return 1
    return n * factorial(n - 1)     # recursive case

for number in [0, 1, 5, 10]:
    print(f"{number}! = {factorial(number)}")

خروجی:

0! = 1
1! = 1
5! = 120
10! = 3628800

دقت کنید که شرط پایه را n <= 1 نوشته‌ایم، نه n == 1. به این ترتیب فاکتوریل صفر هم درست محاسبه می‌شود. اگر فقط n == 1 را بررسی می‌کردیم، فراخوانی factorial(0) به ۱-، ۲- و … می‌رفت و هرگز به حالت پایه نمی‌رسید.

پشت صحنه: پشته فراخوانی (Call Stack)

وقتی تابعی صدا زده می‌شود، پایتون یک «قاب» (Frame) برای آن روی پشته فراخوانی می‌سازد که متغیرهای محلی آن را نگه می‌دارد. در بازگشت، هر فراخوانی قاب مخصوص خودش را دارد؛ یعنی n در هر سطح مقدار جداگانه‌ای دارد. فراخوانی‌ها تا رسیدن به حالت پایه روی هم انباشته می‌شوند و بعد به ترتیب عکس از پشته خارج می‌شوند. کد زیر با تورفتگی، این رفت و برگشت را نشان می‌دهد:

def factorial(n, depth=0):
    indent = "    " * depth
    print(f"{indent}factorial({n}) called")
    if n <= 1:
        print(f"{indent}base case -> 1")
        return 1
    result = n * factorial(n - 1, depth + 1)
    print(f"{indent}factorial({n}) returns {result}")
    return result

factorial(4)

خروجی:

factorial(4) called
    factorial(3) called
        factorial(2) called
            factorial(1) called
            base case -> 1
        factorial(2) returns 2
    factorial(3) returns 6
factorial(4) returns 24

در خروجی می‌بینید که ابتدا چهار فراخوانی پشت سر هم باز می‌شوند و هیچ‌کدام جوابی ندارند، چون همه منتظر فراخوانی بعدی هستند. وقتی factorial(1) به حالت پایه می‌رسد، جواب‌ها به عقب برمی‌گردند: ۲، سپس ۶ و در نهایت ۲۴. فهمیدن همین تصویر مهم‌ترین قدم برای تسلط بر بازگشت است. برای آشنایی بیشتر با محدوده متغیرها در هر فراخوانی، آموزش متغیر محلی و سراسری در پایتون را ببینید.

دنباله فیبوناچی: ساده ولی کند

در دنباله فیبوناچی هر عدد مجموع دو عدد قبلی است: ۰، ۱، ۱، ۲، ۳، ۵، ۸ و … . تعریف بازگشتی آن هم ساده است: fib(n) = fib(n-1) + fib(n-2) با دو حالت پایه برای ۰ و ۱. اما این تابع یک مشکل بزرگ دارد: هر فراخوانی، دو فراخوانی دیگر می‌سازد و بسیاری از مقادیر بارها و بارها از نو محاسبه می‌شوند. بیایید تعداد فراخوانی‌ها را بشماریم:

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:              # base cases: fib(0)=0, fib(1)=1
        return n
    return fib(n - 1) + fib(n - 2)

for n in [10, 20, 25]:
    calls = 0
    value = fib(n)
    print(f"fib({n}) = {value}  ({calls:,} calls)")

خروجی:

fib(10) = 55  (177 calls)
fib(20) = 6765  (21,891 calls)
fib(25) = 75025  (242,785 calls)

برای محاسبه fib(25) بیش از ۲۴۰ هزار فراخوانی انجام شده است. تعداد فراخوانی‌ها تقریباً با هر واحد افزایش n، ۱.۶ برابر می‌شود؛ یعنی پیچیدگی زمانی این روش نمایی است و برای n حدود ۴۰ چند ثانیه طول می‌کشد.

سریع‌تر کردن بازگشت با Memoization و lru_cache

راه‌حل، به خاطر سپردن جواب‌هایی است که قبلاً محاسبه شده‌اند؛ به این تکنیک Memoization می‌گویند. می‌توانید خودتان یک دیکشنری برای ذخیره نتایج بسازید یا از دکوراتور آماده functools.lru_cache استفاده کنید که همین کار را خودکار انجام می‌دهد. اگر با دکوراتورها آشنا نیستید، آموزش دکوراتور در پایتون را بخوانید.

import functools

memo = {}

def fib_memo(n):
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

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

print(fib_memo(80))
print(fib_cached(80))
print(fib_cached.cache_info())

خروجی:

23416728348467685
23416728348467685
CacheInfo(hits=78, misses=81, maxsize=None, currsize=81)

حالا fib(80) در کسری از ثانیه محاسبه می‌شود و طبق cache_info فقط ۸۱ بار محاسبه واقعی انجام شده است. این الگو در برنامه‌نویسی پویا (Dynamic Programming) بسیار پرکاربرد است: اول راه‌حل بازگشتی را بنویسید و اگر محاسبات تکراری دارد، آن را کش کنید.

چند مثال کاربردی و رایج

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

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

def reverse(text):
    if len(text) <= 1:
        return text
    return reverse(text[1:]) + text[0]

def is_palindrome(word):
    word = word.lower()
    if len(word) <= 1:
        return True
    if word[0] != word[-1]:
        return False
    return is_palindrome(word[1:-1])

print(digit_sum(98765))
print(reverse("python"))
print(is_palindrome("Level"), is_palindrome("Python"))

خروجی:

35
nohtyp
True False

در تابع reverse از برش رشته (Slicing) استفاده کرده‌ایم: text[1:] همه حروف به جز حرف اول را برمی‌گرداند. در is_palindrome هم دو حالت پایه داریم: رشته خالی یا تک‌حرفی که پالیندروم است و حروف اول و آخر نابرابر که قطعاً پالیندروم نیست.

کار با داده‌های تودرتو؛ جایی که بازگشت می‌درخشد

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

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))   # go one level deeper
        else:
            result.append(item)
    return result

folder = {
    "notes.txt": 12,
    "photos": {"trip.jpg": 2400, "family.png": 1800},
    "projects": {
        "app.py": 8,
        "data": {"users.json": 40, "logs.csv": 350},
    },
}

def folder_size(tree):
    total = 0
    for name, value in tree.items():
        if isinstance(value, dict):
            total += folder_size(value)
        else:
            total += value
    return total

print(flatten([1, [2, 3], [4, [5, [6, 7]]], 8]))
print("Total size:", folder_size(folder), "KB")

خروجی:

[1, 2, 3, 4, 5, 6, 7, 8]
Total size: 4610 KB

تابع folder_size همان منطقی را دارد که ابزارهای واقعی برای محاسبه حجم پوشه استفاده می‌کنند. در پروژه مرتب‌سازی خودکار فایل‌ها با پایتون می‌توانید همین ایده را روی پوشه‌های واقعی با ماژول os یا pathlib پیاده کنید. کار با فایل‌های JSON هم معمولاً به همین الگو نیاز دارد.

جستجوی دودویی بازگشتی (Binary Search)

جستجوی دودویی در یک لیست مرتب، هر بار نیمی از داده‌ها را کنار می‌گذارد. عنصر وسط را با مقدار مورد نظر مقایسه می‌کنیم؛ اگر برابر بود پیدا شده، اگر کوچک‌تر بود در نیمه راست و اگر بزرگ‌تر بود در نیمه چپ دوباره جستجو می‌کنیم. این تعریف ذاتاً بازگشتی است:

def binary_search(items, target, low=0, high=None):
    if high is None:
        high = len(items) - 1
    if low > high:                 # base case: not found
        return -1
    mid = (low + high) // 2
    if items[mid] == target:       # base case: found
        return mid
    if items[mid] < target:
        return binary_search(items, target, mid + 1, high)
    return binary_search(items, target, low, mid - 1)

scores = [3, 8, 15, 21, 34, 42, 57, 63, 78, 91]
print(binary_search(scores, 42))
print(binary_search(scores, 50))

خروجی:

5
-1

برای لیستی با یک میلیون عنصر، جستجوی دودویی حداکثر حدود ۲۰ مقایسه لازم دارد؛ بنابراین عمق بازگشت هم کم می‌ماند و خطری از نظر حد بازگشت ندارد.

خطای RecursionError و حد بازگشت پایتون

پایتون برای جلوگیری از پر شدن حافظه، عمق بازگشت را محدود می‌کند. مقدار پیش‌فرض این حد معمولاً ۱۰۰۰ است. اگر حالت پایه را فراموش کنید یا ورودی خیلی بزرگ باشد، با خطای RecursionError: maximum recursion depth exceeded روبه‌رو می‌شوید. کد زیر هم حد فعلی را نشان می‌دهد و هم خطا را با try و except مدیریت می‌کند:

import sys

print("Recursion limit:", sys.getrecursionlimit())

def no_base_case(n):
    return no_base_case(n + 1)      # never stops

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

try:
    no_base_case(1)
except RecursionError as error:
    print("RecursionError:", error)

try:
    factorial(5000)
except RecursionError:
    print("factorial(5000) is too deep for the default limit")

خروجی:

Recursion limit: 1000
RecursionError: maximum recursion depth exceeded
factorial(5000) is too deep for the default limit

افزایش حد با sys.setrecursionlimit ممکن است، اما راه‌حل اصلی نیست؛ چون اگر خیلی زیاد شود ممکن است برنامه کاملاً از کار بیفتد. راه درست، بررسی حالت پایه و در صورت نیاز تبدیل تابع به نسخه حلقه‌ای است. توضیح کامل علت‌ها و روش‌های رفع این خطا را در آموزش رفع خطای RecursionError در پایتون ببینید.

بازگشت یا حلقه؟ کدام را انتخاب کنیم

هر تابع بازگشتی را می‌توان با حلقه هم نوشت و برعکس. انتخاب بین این دو به خوانایی و نوع مسئله بستگی دارد. پایتون برخلاف بعضی زبان‌ها بهینه‌سازی «بازگشت انتهایی» (Tail Call) ندارد؛ پس برای تکرارهای طولانی و ساده، حلقه هم سریع‌تر است و هم به حد بازگشت برخورد نمی‌کند:

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def factorial_rec(n):
    return 1 if n <= 1 else n * factorial_rec(n - 1)

print(factorial_loop(20) == factorial_rec(20))
print(len(str(factorial_loop(1000))), "digits in 1000!")

خروجی:

True
2568 digits in 1000!

• بازگشت مناسب است وقتی داده درختی یا تودرتو است (پوشه‌ها، JSON، درخت تصمیم)، الگوریتم ذاتاً «تقسیم و حل» است (جستجوی دودویی، مرتب‌سازی ادغامی) یا تعریف مسئله بازگشتی است.
• حلقه مناسب است وقتی فقط یک شمارش یا تکرار ساده دارید، تعداد تکرارها ممکن است از چند هزار بیشتر شود یا سرعت برایتان اهمیت زیادی دارد.
• در عمل، کد خوانا اولویت دارد. اگر نسخه بازگشتی کوتاه‌تر و قابل‌فهم‌تر است و عمق آن کم می‌ماند، از آن استفاده کنید.

اشتباهات رایج در نوشتن تابع بازگشتی

• نداشتن حالت پایه یا شرط پایه اشتباه: مثل n == 1 برای ورودی صفر یا منفی که باعث بازگشت بی‌پایان می‌شود.
• کوچک نشدن ورودی: اگر در گام بازگشتی ورودی به سمت حالت پایه حرکت نکند (مثلاً f(n) به جای f(n - 1))، تابع هرگز تمام نمی‌شود.
• فراموش کردن return: نوشتن factorial(n - 1) بدون return باعث می‌شود تابع None برگرداند.
• محاسبات تکراری: مثل فیبوناچی ساده؛ با lru_cache حل می‌شود.
• استفاده از لیست قابل‌تغییر به‌عنوان مقدار پیش‌فرض: مثل def f(items=[]) که بین فراخوانی‌ها مشترک می‌ماند؛ به‌جای آن از None استفاده کنید.

تمرین

یک تابع بازگشتی به نام power(base, exp) بنویسید که توان را بدون عملگر ** محاسبه کند. سپس آن را بهینه کنید: اگر توان زوج بود، power(base, exp // 2) را یک بار حساب کنید و در خودش ضرب کنید. در تمرین دوم تابعی بنویسید که همه کلیدهای یک دیکشنری تودرتو را در هر عمقی پیدا کند. برای تمرین‌های بیشتر، ۵۰ تمرین پایتون با جواب را ببینید.

سوالات متداول

تابع بازگشتی در پایتون چیست؟

تابعی است که برای حل مسئله، خودش را با ورودی کوچک‌تر صدا می‌زند تا به حالت پایه برسد؛ سپس جواب‌ها به عقب برمی‌گردند و با هم ترکیب می‌شوند.

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

حالت پایه شرطی است که در آن تابع بدون صدا زدن دوباره خودش جواب را برمی‌گرداند. بدون آن، بازگشت تمام نمی‌شود و پایتون خطای RecursionError می‌دهد.

حد بازگشت در پایتون چقدر است؟

مقدار پیش‌فرض معمولاً ۱۰۰۰ است و با sys.getrecursionlimit دیده می‌شود. افزایش آن با sys.setrecursionlimit ممکن است، اما بهتر است حالت پایه را بررسی کنید یا از حلقه استفاده کنید.

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

برای یادگیری، نسخه بازگشتی تعریف ریاضی را بهتر نشان می‌دهد؛ اما برای اعداد بزرگ، حلقه یا math.factorial سریع‌تر است و به حد بازگشت برخورد نمی‌کند.

چرا فیبوناچی بازگشتی کند است؟

چون هر فراخوانی دو فراخوانی دیگر می‌سازد و مقادیر تکراری بارها محاسبه می‌شوند. با Memoization یا دکوراتور functools.lru_cache زمان اجرا به‌شدت کم می‌شود.

بازگشت در چه مسائلی بیشترین کاربرد را دارد؟

در داده‌های درختی و تودرتو مثل پوشه‌ها و JSON، الگوریتم‌های تقسیم و حل مثل جستجوی دودویی و مرتب‌سازی ادغامی و مسائل ترکیبیاتی مثل تولید جایگشت‌ها.

آموزش‌های مرتبط

• دوره پایتون سطح متوسط
• تعریف تابع با def و return
• رفع خطای RecursionError در پایتون
• دکوراتور در پایتون
• تابع lambda در پایتون
• آموزش جامع پایتون از صفر تا پیشرفته