Recursive Functions (توابع بازگشتی)

[Alireza.AM]

مقدمه

در مورد این توابع در کتابهای مختلف مطالب بسیاری نوشته شده‌است ولی معمولا برنامه‌نویسهای نه‌چندان کهنه‌کار با نوشتن این‌گونه توابع مشکلاتی دارند که به نظر من این مشکلات از آشنایی نه چندان کافی با مفهوم Recursion ناشی می‌شوند.

تابعی که خودش را صدا کند یک تابع بازگشتی و یا Recursive است، بنابراین تشخیص یک تابع بازگشتی کار سختی نیست،‌کافی است که در متن کد یک تابع نام خودش را مشاهده کنید، این یعنی که ما با یک تابع بازگشتی سرو کار داریم. البته این اصلا تعریف آکادمیکی نیست ولی شاید در بعضی موارد به برخی مخاطب‌های این متن کمک کند.

شاید در مورد Trigger های SQL اصطلاحات Direct Recursion و Indirect Recursion را شنیده باشید، می‌خواهم بگویم که مفاهیم بازگشت مستقیم و غیر مستقیم در مورد توابع هم صدق می‌کنند، به این معنی که اگر تابعی خودش خودش را صدا کند باعث یک Direct Recursion شده است ولی اگر تابع یک، تابع دو را صدا کند و تابع دو تابع یک را صدا بزند این پروسه موجب یک Indirect Recursion می‌شود.


Sample Scenario

یک Tree Control را در نظر بگیرید، نگران نشوید موضوع پیچیده نیست منظورم یک شی مثل Windows Explorer است که Folder ها را در یک ساختار درختی نمایش می‌دهد فقط همین، فرض می‌کنیم که هریک از Node های موجود در این درخت یک Property به نام ID دارند مثل اکثر Object ها که یک مشخصه به نام ID دارند، ما می‌خواهیم تابعی بنویسیم که با گرفتن یک ID جستجو بکند و Node مربوط به آن ID را برای ما برگرداند.

یک مثال ساده از توابع بازگشتی، مثال تابع فاکتوریل است که نمونه ++C آن را اینجا نوشته‌ام:

int Factorial(int a)
{
if (a>1)
{
return (a * Factorial(a-1));
}
else
{
return 1;
}
}

استفاده از توابع بازگشتی مثل بقیه توابع است، یعنی فقط Call می‌شوند همین:

cout << Factorial(3) <<"\n";

Sample Code

آین کد برای VB.NET نوشته شده است اگر به syntax دیگری نیاز داشتید به من اطلاع بدهید
همینطور که ملاحظه می‌کنید این تابع دو ورودی می‌گیرد،‌ یک Node به عنوان نقطه شروع جستجو و یک ID به عنوان مشخصه Node مورد جستجو.

توجه داشته باشید که هیچ محدودیتی در Hierarchy وجود ندارد یعنی هر Node می‌تواند بی‌نهایت Node به عنوان فرزند داشته باشد و همچنین هریک از فرزندها . اصلا به همین دلیل است که ما به یک تابع یازگشتی نیاز داریم.

Private Function FindNodeByIDinTree(StartNode as treeNodeObject,ID as string)

Dim M as TreeNode
Dim n as TreeNode
if StartNode.ID = ID then
Return StartNode
else
If StartNode.nodes.count <>o then
for each n in StartNode.nodes
m = FindNodeByIDinTree (n,ID)
If not m is nothing then
return m
End If
next
else
retirn nothing
end if
end if

End Function

[hirsoft]

عرض خسته نباشی مفهوم Hierarchy که در قطعه sample code بیشتر توضیح دهید ممنون

[Alireza.AM]

منظور از Hierarchy ترتیب (سلسه مراتب) است. منطور از جمله:

"هیچ محدودیتی در Hierarchy وجود ندارد یعنی هر Node می‌تواند بی‌نهایت Node به عنوان فرزند داشته باشد و همچنین هریک از فرزندها"

این است که هیچ محدودیتی در این ساختار وجود ندارد و هر Node می‌تواند زیرمجموعه‌های خودش را داشته باشد.