شناسایی اجزای اصلی بازگشت: شرط پایه و حالت بازگشتی
پیاده‌سازی بازگشتی فاکتوریل، فیبوناچی، مجموع و توان
تحلیل پشته‌ی فراخوانی (Call Stack) برای یک تابع بازگشتی
مقایسه‌ی بازگشت و حلقه و تشخیص زمان استفاده از هر کدام
تابع بازگشتی چیست؟
تابع بازگشتی (Recursive Function) تابعی است که خودش را صدا می‌زند. این روش برای حل مسائلی مناسب است که می‌توان آن‌ها را به نسخه‌ی کوچک‌ترِ همان مسئله تقسیم کرد.
ایده‌ی اصلی:
اگر مسئله به اندازه‌ی کافی کوچک است → حل مستقیم (شرط پایه)
در غیر این صورت → نسخه‌ی کوچک‌تر را با همان تابع حل کن (فراخوانی بازگشتی)
به مثال کلاسیک فاکتوریل توجه کنید:
n! = n × (n-1)!
پس برای محاسبه‌ی n! کافی است (n-1)! را حساب کنیم، یعنی همان مسئله ولی با ورودی کوچک‌تر. این یک ویژگی طبیعی برای بازگشت است.
دو بخش حیاتی هر بازگشت
هر تابع بازگشتی دو بخش ضروری دارد. فراموش کردن هر کدام فاجعه‌بار است:
۱. شرط پایه (Base Case): کوچک‌ترین حالت مسئله که جواب مستقیم و مشخص است. این شرط پایان بازگشت را تعیین می‌کند.
۲. حالت بازگشتی (Recursive Case): فراخوانی تابع با ورودی کوچک‌تر، به همراه ترکیب نتیجه با مقدار فعلی.
main.cppcpp
بدون شرط پایه، تابع بی‌نهایت بار خودش را صدا می‌زند تا حافظه‌ی پشته تمام شود.
پیاده‌سازی بازگشتی فاکتوریل
این کد مستقیماً از فرمول n! = n × (n-1)! پیروی می‌کند. شرط پایه n == 1 است (می‌توان n <= 1 گرفت تا 0! = 1 هم درست باشد).
int fact(int n) با شرط پایه n == 1cpp
$خروجی برنامه
5! = 120
تحلیل پشته‌ی فراخوانی برای fact(4)
این نمودار نشان می‌دهد وقتی fact(4) صدا زده می‌شود، پشته‌ی فراخوانی (Call Stack) چگونه شکل می‌گیرد و سپس باز می‌گردد. هر فراخوانی، یک نسخه‌ی جدید از تابع روی پشته می‌سازد تا شرط پایه برقرار شود.
flow.svg
ردیابی گام‌به‌گام fact(5)
برای درک بهتر، fact(5) را گام‌به‌گام دنبال می‌کنیم. خروجی نهایی باید ۱۲۰ باشد.
main.cppcpp
بازگشت از دو فاز تشکیل می‌شود:
فاز فراخوانی (Winding): از fact(5) تا fact(1) به پایین می‌رویم.
فاز بازگشت (Unwinding): از fact(1) تا fact(5) به بالا برمی‌گردیم و جواب‌ها را ترکیب می‌کنیم.
خطر سرریز پشته (Stack Overflow)
اگر شرط پایه را ننویسید یا اشتباه بنویسید، تابع بی‌نهایت خودش را صدا می‌زند. هر فراخوانی، حافظه‌ای روی پشته (Stack) اشغال می‌کند. وقتی پشته پر شود، برنامه با خطای Stack Overflow کرش می‌کند.
مثال خطرناک:
main.cppcpp
این تابع هرگز متوقف نمی‌شود تا جایی که پشته سرریز می‌شود.
نکات ایمنی:
همیشه مطمئن شوید شرط پایه برای تمام ورودی‌های ممکن برقرار می‌شود.
برای اعداد منفی یا صفر هم بررسی کنید (مثلاً if (n <= 1) به‌جای if (n == 1)).
هر فراخوانی بازگشتی باید مسئله را به ورودی کوچک‌تر ببرد تا به شرط پایه برسد.
بازگشت فیبوناچی
دنباله‌ی فیبوناچی به این شکل تعریف می‌شود:
F(0) = 0 و F(1) = 1 (شرط‌های پایه)
F(n) = F(n-1) + F(n-2) برای n ≥ 2
این مسئله نمونه‌ی کلاسیک بازگشت است، اما یک نقص بزرگ دارد: محاسبه‌ی تکراری. مثلاً برای F(5) نیاز به F(4) و F(3) داریم؛ اما F(4) خودش F(3) را هم محاسبه می‌کند. یعنی F(3) دو بار محاسبه می‌شود!
برای اعداد بزرگ این موضوع به‌شدت کند می‌شود. راه‌حل استفاده از Memoization (حفظ نتایج) یا استفاده از نسخه‌ی حلقه‌ای است.
پیاده‌سازی بازگشتی فیبوناچی
توجه کنید این نسخه ساده‌ترین شکل بازگشتی است و برای n بزرگ (مثلاً n > 40) بسیار کند می‌شود. برای کاربرد عملی از نسخه‌ی حلقه‌ای یا memoization استفاده کنید.
می‌خواهیم S(n) = 1 + 2 + 3 + ... + n را به‌صورت بازگشتی بنویسیم.
شرط پایه:S(1) = 1
حالت بازگشتی:S(n) = n + S(n-1)
این الگو کاملاً شبیه فاکتوریل است، با این تفاوت که به‌جای ضرب، جمع داریم. نتیجه با فرمول n*(n+1)/2 یکسان است.
پیاده‌سازی بازگشتی مجموع ۱ تا n
این تابع مجموع اعداد ۱ تا n را به‌صورت بازگشتی محاسبه می‌کند. برای n=10 باید 55 چاپ شود.
int sum(int n) با شرط پایه n == 1cpp
$خروجی برنامه
n ra vared konid: 10
majmoo 1 ta 10 = 55
مثال: توان (Power)
می‌خواهیم pow(x, n) = x^n را به‌صورت بازگشتی بنویسیم (n غیر منفی).
شرط پایه:x^0 = 1
حالت بازگشتی:x^n = x × x^(n-1)
می‌توان با تقسیم مسئله این را سریع‌تر هم کرد (x^n = (x^(n/2))² اگر n زوج باشد) که به آن Exponentiation by Squaring می‌گویند و پیچیدگی را از O(n) به O(log n) می‌رساند.
پیاده‌سازی بازگشتی توان
نسخه‌ی ساده بازگشتی توان. برای اعداد بزرگ‌تر از نسخه‌ی سریع (Exponentiation by Squaring) استفاده کنید.
long long power(int x, int n)cpp
$خروجی برنامه
2^10 = 1024
5^3 = 125
نسخه‌ی سریع توان با Exponentiation by Squaring
این نسخه از ویژگی x^n = (x²)^(n/2) برای اعداد زوج و x^n = x × (x²)^((n-1)/2) برای اعداد فرد استفاده می‌کند و تعداد فراخوانی‌ها را به‌شدت کاهش می‌دهد. برای n=50 این نسخه حدود ۶ فراخوانی می‌کند در حالی که نسخه‌ی ساده ۵۰ فراخوانی!
پیچیدگی O(log n) به‌جای O(n)cpp
$خروجی برنامه
2^50 = 1125899906842624
بازگشت در برابر حلقه
هر مسئله‌ی بازگشتی را می‌توان با حلقه و برعکس پیاده کرد. انتخاب کدام روش به خوانایی و کارایی بستگی دارد.
بازگشت معمولاً کوتاه‌تر و خواناتر است، به‌ویژه برای مسائل بازگشتی طبیعی (مثل پیمایش درخت، تقسیم و غلبه).
حلقه معمولاً سریع‌تر و بهینه‌تر است زیرا از پشته استفاده نمی‌کند.
در مسائل ساده مثل فاکتوریل و فیبوناچی، نسخه‌ی حلقه‌ای ترجیح داده می‌شود.
نسخه اشتباه جزوه
کد دارای باگcpp
نسخه اصلاح‌شده و استاندارد
کد صحیحcpp
چه وقت از بازگشت استفاده کنیم؟
از بازگشت استفاده کنید وقتی:
مسئله به‌طور طبیعی بازگشتی است (درخت، گراف، تقسیم و غلبه)
خوانایی مهم‌تر از کارایی است (کد آموزشی یا الگوریتم پیچیده)
عمق بازگشت کم است (کمتر از چند هزار)
از حلقه استفاده کنید وقتی:
مسئله ساده و خطی است (فاکتوریل، مجموع، فیبوناچی)
کارایی حیاتی است
عمق بازگشت زیاد است (مثلاً n > 10000)
نکته: در C++ می‌توان با فعال کردن بهینه‌سازی کامپایلر (مثل -O2)، برخی توابع بازگشتی به‌صورت خودکار به حلقه تبدیل می‌شوند (Tail Call Optimization). برای این کار باید فراخوانی بازگشتی آخرین کاری باشد که تابع انجام می‌دهد.
اشتباهات رایج در بازگشت
فراموش کردن شرط پایه → سرریز پشته و کرش برنامه.
شرط پایه‌ی نادرست که هرگز برقرار نمی‌شود (مثلاً شروع از n = 0 ولی شرط n == 1).
فراخوانی با ورودی غیرکوچک‌تر (مثلاً fact(n + 1) به‌جای fact(n - 1)) — تابع به‌جای نزدیک شدن به شرط پایه، از آن دور می‌شود!
محاسبه‌ی تکراری مثل فیبوناچی ساده — برای اعداد بزرگ به‌شدت کند می‌شود.
عمق بیش از حد — ویندوز معمولاً حدود ۱MB پشته دارد. اگر هر فراخوانی ۱۰۰ بایت اشغال کند، بیشترین عمق حدود ۱۰۰۰۰ است.
عدم اعتبارسنجی ورودی مثل fact(-5) که به حلقه‌ی بی‌نهایت منجر می‌شود.
مثال پیشرفته: چاپ معکوس یک رشته با بازگشت
این یک استفاده‌ی هوشمندانه از پشته‌ی بازگشت است: اول به‌صورت بازگشتی تا آخر رشته می‌رویم، سپس در فاز بازگشت، کاراکتر‌ها را چاپ می‌کنیم. این کار معادل استفاده از یک آرایه‌ی کمکی است، اما به‌صورت خودکار توسط پشته مدیریت می‌شود.
تابع بازگشتی `void countdown(int n)` بنویسید که اعداد از n تا ۱ را به ترتیب نزولی چاپ کند. مثلاً `countdown(5)` باید `5 4 3 2 1` چاپ کند. در `main` آن را با n=5 صدا بزنید.
نمایش راهنما
ابتدا `cout << n`، سپس اگر `n > 1` آن‌گاه `countdown(n - 1)` را صدا بزنید.
02
تمرین•حل کامل دارد
تابع بازگشتی `int sumDigits(int n)` بنویسید که مجموع ارقام یک عدد صحیح مثبت را برگرداند. مثلاً `sumDigits(1234)` باید ۱۰ برگرداند.
نمایش راهنما
رقم آخر `n % 10` است و بقیه‌ی عدد `n / 10`. شرط پایه: اگر `n < 10` آن‌گاه `n` را برگردانید.
03
تمرین•حل کامل دارد
تابع بازگشتی `long long power(int x, int n)` بنویسید که `x` به توان `n` را محاسبه کند. شرط پایه: `x^0 = 1`. در `main` مقدار `2^10` را چاپ کنید.
تابع بازگشتی `int fib(int n)` بنویسید که nامین جمله فیبوناچی را برگرداند. `fib(0) = 0`، `fib(1) = 1`، `fib(n) = fib(n-1) + fib(n-2)`. در `main` اعضای ۰ تا ۱۰ دنباله را چاپ کنید.
نمایش راهنما
دو شرط پایه لازم است: `n == 0` برمی‌گرداند `0` و `n == 1` برمی‌گرداند `1`. سپس `fib(n-1) + fib(n-2)` را برگردانید.
05
تمرین•حل کامل دارد
تابع بازگشتی `void printReverse(const string &s, int i = 0)` بنویسید که یک رشته را به‌صورت معکوس چاپ کند (بدون ساخت رشته‌ی جدید). در `main` کلمه‌ای را از ورودی بگیرید و معکوس آن را چاپ کنید.
نمایش راهنما
ابتدا تا آخر رشته بروید (فراخوانی بازگشتی)، سپس در فاز بازگشت `s[i]` را چاپ کنید. شرط پایه: `i == s.length()`.
// نکات-کلیدی۶
01تابع بازگشتی تابعی است که خودش را صدا می‌زند تا نسخه‌ی کوچک‌تری از همان مسئله را حل کند.
02هر تابع بازگشتی باید **شرط پایه** داشته باشد تا از فراخوانی بی‌نهایت جلوگیری شود؛ بدون آن Stack Overflow رخ می‌دهد.
03فاکتوریل `n! = n × (n-1)!` یک مثال کلاسیک بازگشت است که خوانایی بالایی دارد.
04هر فراخوانی بازگشتی حافظه‌ای روی پشته (Stack) اشغال می‌کند؛ برای عمق زیاد، نسخه‌ی حلقه‌ای ترجیح داده می‌شود.
05مسائلی مثل فیبوناچی ساده، دارای محاسبه‌ی تکراری هستند و با Memoization یا نسخه‌ی حلقه‌ای بهینه می‌شوند.
06بازگشت برای مسائل طبیعی بازگشتی (پیمایش درخت، تقسیم و غلبه، Backtracking) بهترین انتخاب است، در حالی که برای حلقه‌های خطی ساده، حلقه بهتر است.
آخرین درس این دسته را تمام کردی — وقت آن است که همه‌چیز را یک‌جا به محک بزنی. سیستم کوچکی بساز که n دانشجو را با struct (نام، شماره، معدل) در حافظهٔ پویا نگه دارد. منویی با do-while بدهد: ثبت، حذف، فهرست مرتب بر اساس معدل، بهترین دانشجو (با اشاره‌گر)، و میانگین کل با یک تابع بازگشتی روی آرایه. پیش از خروج، حافظه کاملاً آزاد شود.
⏱ ۲ تا ۳ ساعت۶ نیازمندی — هر کدام به یک درس لینک است
نام درس، موضوع یا کلمه کلیدی را بنویسید و با Enter به آن بروید
intfact(int n){if(n ==1)// شرط پایهreturn1;elsereturn n *fact(n -1);// حالت بازگشتی}
1#include<iostream>2usingnamespace std;34longlongfact(int n){5if(n <=1)6return1;// شرط پایه: 0! و 1! هر دو برابر 17else8return n *fact(n -1);// حالت بازگشتی9}1011intmain(){12int n =5;13 cout << n <<"! = "<<fact(n)<< endl;// 12014return0;15}
flow.svg100%
Press enter or space to select a node. You can then use the arrow keys to move the node around. Press delete to remove it and escape to cancel.
Press enter or space to select an edge. You can then press delete to remove it or escape to cancel.
شروع/پایانپردازشتصمیمورودی/خروجی
fact(5)=5 × fact(4)fact(4)=4 × fact(3)fact(3)=3 × fact(2)fact(2)=2 × fact(1)fact(1)=1 ← شرط پایه
حالا از پایین به بالا جواب را می‌سازیم:fact(2)=2 × 1=2fact(3)=3 × 2=6fact(4)=4 × 6=24fact(5)=5 × 24=120 ✓
intfact(int n){return n *fact(n -1);// بدون شرط پایه!}
1#include<iostream>2usingnamespace std;34longlongfib(int n){5if(n ==0)return0;// شرط پایه ۱6if(n ==1)return1;// شرط پایه ۲7returnfib(n -1)+fib(n -2);// حالت بازگشتی8}910intmain(){11for(int i =0; i <=10; i++)12 cout <<"fib("<< i <<") = "<<fib(i)<< endl;13return0;14}
1#include<iostream>2usingnamespace std;34longlongsum(int n){5if(n ==1)return1;// شرط پایه6return n +sum(n -1);// حالت بازگشتی7}89intmain(){10int n;11 cout <<"n ra vared konid: ";12 cin >> n;13 cout <<"majmoo 1 ta "<< n <<" = "<<sum(n)<< endl;14return0;15}
1#include<iostream>2usingnamespace std;34longlongpower(int x,int n){5if(n ==0)return1;// شرط پایه: هر چیزی به توان ۰ برابر ۱6return x *power(x, n -1);// حالت بازگشتی7}89intmain(){10 cout <<"2^10 = "<<power(2,10)<< endl;// 102411 cout <<"5^3 = "<<power(5,3)<< endl;// 12512return0;13}
1#include<iostream>2usingnamespace std;34longlongfastPow(longlong x,longlong n){5if(n ==0)return1;6if(n %2==0){7longlong half =fastPow(x, n /2);8return half * half;9}else{10return x *fastPow(x, n -1);11}12}1314intmain(){15 cout <<"2^50 = "<<fastPow(2,50)<< endl;16return0;17}
1// نسخه‌ی بازگشتی فاکتوریل2// مزیت: خوانا، نزدیک به تعریف ریاضی3// معیب: حافظه‌ی پشته مصرف می‌کند،4// برای n بزرگ خطر Stack Overflow5longlongfact(int n){6if(n <=1)return1;7return n *fact(n -1);8}
1// نسخه‌ی حلقه‌ای فاکتوریل2// مزیت: سریع، بدون خطر سرریز پشته3// معیب: کمی طولانی‌تر از نسخه بازگشتی4longlongfact(int n){5longlong p =1;6for(int i =1; i <= n; i++)7 p *= i;8return p;9}
1#include<iostream>2#include<string>3usingnamespace std;45voidprintReverse(const string &s,int i){6if(i ==(int)s.length())return;// شرط پایه7printReverse(s, i +1);// ابتدا به انتهای رشته برو8 cout << s[i];// سپس در فاز بازگشت چاپ کن9}1011intmain(){12 string s;13 cout <<"reshte: ";14 cin >> s;15 cout <<"makoose: ";16printReverse(s,0);17 cout << endl;18return0;19}