چه طور میشه یه برنامه رو به صورت بازگشتی نوشت

[maha19]

میشه یه نفر قشنگ توضیح بده چه طور میتونیم یه برنامه رو به صورت بازگشتی بنویسیم
چه قوانینی رو باید رعایت کنیم
ممنون میشم توضیح بدین

[La Volpe]

تعاریف بازگشتی تعاریفی هستن که خودشون، خودشون رو صدا می زنن! مثلا تو ریاضی سری Xn=2+3Xn یه سری بازگشتیه!
تو C++‎‎‎‎ و کلا برنامه نویسی، توابعی که داخل تابع از خود تابع استفاده میشه! مثلا این مثال برای برنامه ی محاسبه ی فاکتوریل هست:

#include <iostream>
using namespace std;

long factorial (long a)
{
if (a > 1)
return (a * factorial (a-1));
else
return 1;
}

int main ()
{
long number = 9;
cout << number << "! = " << factorial (number);
return 0;
}


میدونیم که فاکتوریل تعریفش هست: a!=a*(a-1)! و با فرض اینکه 1!=1 یعنی وقتی من به 1 رسیدم بلافاصله نتایج رو در 1 ضرب می کنم! مثلا به ازای 5 ، برنامه اینجوری عمل می کنه!:
اول من مقدار 5 رو بهش می دم، برنامه چک می کنه که آیا از یک بزرگتره یا نه؟ که پاسخ مثبته! برنامه می ره تا رو در 4 فاکتوریل ضربش کنه، که باز بر می گرده ببینه 4 بزرگتر از 1 هست که باز هم درسته، شروع می کنه به محاسبه ی 4 فاکتوریل که خودش هست 4 ضرب در 3 فاکتوریل، 3 هم از 1 بزرگتره(دقت، که در داخل تابع، مجددا از تابع استفاده میشه)، برنامه باید 3 رو در دو فاکتوریل ضرب کنه که خود 2 فاکتوریل هم ضرب 2 در یک فاکتوریل هست! اما چون 1 از یک بزرگتر نیست، برنامه تمام نتایج رو در یک ضرب می کنه تا متوقف شه! حالا این پروسه به بیرون می ره، یعنی خروجی 1 فاکتوریل در 2، خروجی 2 فاکتوریل در 3، خروچی سه فاکتوریل در 4، و دست آخر هم خروجی 4 فاکتوریل در 5 ضرب میشه! به عبارتی 5*4*3*2*1 که خوب میشه 120! یا بهتر:

5!=5*4!
4!=4*3!
3!=3*2!
2!=2*1!
1!=1با دقت تو این مثال می فهمی که بازگشتی ها وقتی به کار میان(یا بهتر بگم: وقتی می تونیم ازشون استفاده کنیم) که:
1. در خود تعریف نیاز به اینکار باشه، مثلا دنباله ها، سری ها و... مثل همون تعریف سری، یا همین فاکتوریل که شرحش رو نوشتم!
2. هر تعریفی که به صورت بازگشتی باشه رو نمیشه به صورت بازگشتی نوشت! یه نکته باید رعایت کنی اونم اینه که حتما و حتما باید یه نقطه ی مینیمم(این واژه علمی نیست، من بهش اینطور میگم!تو کتابی که من خونده بودم، نوشته بود حالت توقف!) تو تعریف داشته باشیم! مثلا تو فاکتوریل نقطه ی a=1 که خوب 1!=1 و نقطه ی پایانه! یا مثلا تو فیبوناچی، نقطه ی f(1)= 1 و f(2)=1 یعنی وقتی به این دو مقدار می رسه تابع متوقف میشه و عقبتر نمی ره! چرا؟ خوب واضحه! اگه مثلا تو همین فاکتوریل، ما نقطه ی 1 رو تعیین نمی کردیم، این برنامه به یه حلقه ی بی پایان (Infinite Loop) تبدیل می شد و برنامه هیچوقت تموم نمی شد.
واسه تمرین میشه همین فیبوناتچی رو بنویسی! فیبوناتچی یه دنباله است که جمله ی اولش 0، دومش 1 و بقیه جملات از جمع دو جمله ی باقی مانده تشکیل میشه! 0,1,1,2,3,5,8,11,... سعی کن اینو به صورت بازگشتی بنویسی! راهنمایی هم:

long fibo(int n)
{
...
...
fibo(n-1)+fibo(n-2);
...
}

[hadi0x7c7]

برای ایده های بیشتر به الگوریتم های تقسیم و غلبه و همچنین برنامه نویسی پویا رجوع کنید تا دیدتون بیشتر بشه.

[sourcecode]

میشه یه نفر قشنگ توضیح بده چه طور میتونیم یه برنامه رو به صورت بازگشتی بنویسیم
دوست عزیز به لینک زیر هم یه سری بزن شاید به دردت خورد .
http://www.youtube.com/watch?v=SRGKxUG3XbE