ریکرژن

Recursion یا ریکرژن به معنی بازگشت در برنامه‌نویسی است. در این روش یک تابع مستقیماً یا به شکل غیرمستقیم خودش را برای زیرمسئله کوچک‌تر فراخوانی می‌کند. داشتن شرط توقف و کوچک شدن مسئله برای جلوگیری از حلقه یا فراخوانی بی‌پایان ضروری است.

کاربرد واقعی: مجموع تعداد آیتم‌های دسته‌بندی تو در تو

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

PHP

function countNodes(array $node): int {
    $total = 1;
    foreach ($node['children'] ?? [] as $child) {
        $total += countNodes($child);
    }
    return $total;
}

Python

def count_nodes(node):
    return 1 + sum(count_nodes(c) for c in node.get('children', []))

Go

type Node struct { Children []*Node }
func countNodes(n *Node) int {
    if n == nil { return 0 }
    total := 1
    for _, child := range n.Children { total += countNodes(child) }
    return total
}

C#

static int CountNodes(Node node) => 1 + node.Children.Sum(CountNodes);

ریکرژن یا Iteration؟

اصطلاحات مرتبط: پیمایش، پشته، الگوریتم، ساختار داده.