بازگشت (Recursion)

آینه در آینه

بازگشت (Recursion) یعنی تابعی که برای حل مسئله، خودش را با ورودی کوچک‌تر صدا می‌زند. مثل دو آینه روبه‌رو که تصویر در تصویر می‌سازند!

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

1. شرط پایه (Base Case): حالتی که بدون بازگشت حل می‌شود — نقطه توقف
2. گام بازگشتی: فراخوانی خود با ورودی کوچک‌تر به سمت شرط پایه

مثال کلاسیک: فاکتوریل

فاکتوریل n یعنی: n! = n × (n-1) × ... × 2 × 1

تعریف بازگشتی: n! = n × (n-1)! و شرط پایه: 0! = 1

function Factorial(n: integer): integer;
begin
  if n <= 1 then
    Result := 1                    { شرط پایه }
  else
    Result := n * Factorial(n - 1);  { گام بازگشتی }
end;

اجرای Factorial(4):

Factorial(4) = 4 * Factorial(3)
             = 4 * 3 * Factorial(2)
             = 4 * 3 * 2 * Factorial(1)
             = 4 * 3 * 2 * 1
             = 24

فیبوناچی بازگشتی

function Fib(n: integer): integer;
begin
  if n <= 1 then
    exit(n)                        { پایه: Fib(0)=0, Fib(1)=1 }
  else
    exit(Fib(n-1) + Fib(n-2));     { بازگشتی }
end;

مجموع ارقام بازگشتی

function DigitSum(n: integer): integer;
begin
  if n < 10 then
    exit(n)                        { یک رقم }
  else
    exit((n mod 10) + DigitSum(n div 10));
end;
{ DigitSum(4527) = 7 + DigitSum(452) = 7 + 2 + DigitSum(45) = ... = 18 }

توان بازگشتی

function Power(base, exp: integer): integer;
begin
  if exp = 0 then
    exit(1)
  else
    exit(base * Power(base, exp - 1));
end;

مثلث پاسکال — مناسب نام زبان!

function Comb(n, k: integer): integer;
begin
  if (k = 0) or (k = n) then
    exit(1)
  else
    exit(Comb(n-1, k-1) + Comb(n-1, k));
end;

var i, j: integer;
begin
  for i := 0 to 6 do
  begin
    for j := 0 to i do
      write(Comb(i, j):5);
    writeln;
  end;
end.

بازگشت در برابر حلقه

خلاصه

• بازگشت = تابع که خودش را صدا می‌زند
• شرط پایه الزامی است (وگرنه بی‌نهایت!)
• گام بازگشتی باید به سمت پایه برود
• فاکتوریل، فیبوناچی، مثلث پاسکال = تمرین‌های کلاسیک