Algorithms/Recursion

تسمى العملية التي تستدعي الدالة فيها نفسها استدعاءً مباشرًا أو غير مباشر بالتعاود recursion، وتسمى هذه الدالة بالدالة التعاودية recursive function. يمكن إيجاد الحلول لبعض المسائل بسهولة كبيرة باستخدام خوارزمية التعاود، منها على سبيل المثال: أبراج هانوي Towers of Hanoi، التنقل الوسطي Inorder، والتنقل القبلي Preorder، والتنقل البعدي Postorder في عمليات التنقل عبر عناصر أشجار البيانات Tree Traversals، وخوارزمية البحث بالعمق أولًا في الرسوم البيانية وغيرها.

تقدم البرامج التعاودية حلًّا للحالة الأساس Base Case ويُعرض الحل للمسألة الأكبر على هيئة مسائل أصغر.

int fact(int n)
{
    if (n < = 1) // الحالة الأساس
        return 1;
    else    
        return n*fact(n-1);    
}

الحالة الأساس في المثال السابق هي n <= 1، ويمكن إيجاد الحل لأرقام أكبر عن طريق تحويل القيم إلى قيم أصغر إلى حين الوصول إلى الحالة الأساس.

استخدام التعاود لحل المسائل

تتلخّص فكرة التعاود في تمثيل المسألة على هيئة مسألة أو مسائل أصغر، وإضافة حالة واحدة أو حالات أساس متعددة لإيقاف التعاود. فعلى سبيل المثال، يمكن حساب مضروب العدد n إن كان مضروب العدد n-1 معروفًا، فتكون الحالة الأساس لعملية إيجاد المضروب هي n = 0؛ لذا نعيد القيمة 1 عندما تصبح n=0.

حالة فيضان الكدس

إن لم تصل الدالة إلى الحالة الأساس أو إن كانت الحالة الأساس غير معرفة، فإنّ ذلك سيؤدي إلى حدوث حالة تسمى بفيضان الكدس Stack Overflow. مثال:

int fact(int n)
{
    // حالة أساس خاطئة (قد تتسبب في حدوث فيضان الكدس)
    if (n == 100) 
        return 1;

    else
        return n*fact(n-1);
}

يؤدي استدعاء الدالة fact(10)‎ إلى استدعاء الدوال fact(9)‎ و fact(8)‎ و fact(7)‎ وهكذا، ولن تصل الدالة إلى العدد 100، وهذا يعني عدم الوصول إلى الحالة الأساس، وإن استنزفت الذاكرة جرّاء استدعاء هذه الدوال في مكدس استدعاء الدوال، فإنّ ذلك سيتسبب في حدوث خطأ فيضان المكدس.

التعاود المباشر والتعاود غير المباشر

نقول أن الدالة تعاودية مباشرة إذا كانت تستدعي نفسها. ونقول أن الدالة تعاودية غير مباشرة إذا كانت الدالة تستدعي دالة أخرى وكانت تلك الدالة الأخرى تستدعي الدالة الأولى استدعاءً مباشرًا أو غير مباشر.

مثال:

// دالة تعاودية مباشرة
void directRecFun()
{
    // Some code....

    directRecFun();

    // Some code...
}

// دالة تعاودية غير مباشرة
void indirectRecFun1()
{
    // Some code...

    indirectRecFun2();

    // Some code...
}


// دالة تعاودية غير مباشرة
void indirectRecFun2()
{
    // Some code...

    indirectRecFun1();

    // Some code...
}

الدالة التعاودية المذيلة وغير المذيلة

تكون الدالة التعاودية مذيلة tail-recursion إن كان الاستدعاء التعاودي هو آخر ما تنفّذه الدالة.

void print(int n) 
{ 
	if (n < 0) return; 
	cout << " " << n; 

	// آخر عبارة تنفّذها الدالة هي الاستدعاء التعاودي
	print(n-1); 
}

تعدّ الدوال التعاودية المذيّلة أفضل من تلك غير المذيلة، وذلك لإمكانية تحسين التعاود المذيّل بواسطة المصرّف compiler. وتقوم الفكرة على مبدأ بسيط مفاده أنّه لمّا كان الاستدعاء التعاودي في نهاية الدالة، فهذا يعني أنّه لم يبق شيء يمكن القيام به في هذه الدالة؛ ولا حاجة حينئذٍ لحفظ إطار التعاود الحالي current function's stack frame الخاص بالدالة.

تحويل الدالة التعاودية غير المذيلة إلى مذيلة

تحسب الدالة التالية مضروب العدد المعطى للدالة وليكن n. هذه الدالة دالة تعاودية غير مذيلة. صحيح أنّها قد تبدوا للوهلة الأولى مذيلة، ولكن إمعان النظر فيها يكشف عن أن الاستدعاء fact(n)‎ يستخدم القيمة المعادة بواسطة الاستدعاء fact(n-1)‎، وهذا يعني أنّ الاستدعاء fact(n-1)‎ ليس آخر ما تقوم به الدالة fact(n)‎.

#include<iostream> 
using namespace std; 

// fact(n) يستخدم الاستدعاء
// fact(n-1) القيمة المعادة بواسطة الاستدعاء 
// fact(n-1)‎ وهذا يعني أنّ الاستدعاء
// fact(n)‎ ليس آخر ما تقوم به الدالة

unsigned int fact(unsigned int n) 
{ 
	if (n == 0) return 1; 

	return n*fact(n-1); 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	cout << fact(5); 
	return 0; 
}

• بايثون:

# fact(n) يستخدم الاستدعاء
# fact(n-1) القيمة المعادة بواسطة الاستدعاء 
# fact(n-1)‎ وهذا يعني أنّ الاستدعاء
# fact(n)‎ ليس آخر ما تقوم به الدالة

def fact(n): 

	if (n == 0): 
		return 1

	return n * fact(n-1) 

# اختبار الدالة السابقة
print(fact(5))

• جافا:

class GFG { 
	
	// fact(n) يستخدم الاستدعاء
	// fact(n-1) القيمة المعادة بواسطة الاستدعاء 
	// fact(n-1)‎ وهذا يعني أنّ الاستدعاء
	// fact(n)‎ ليس آخر ما تقوم به الدالة

	static int fact(int n) 
	{ 
		if (n == 0) return 1; 
	
		return n*fact(n-1); 
	} 
	
	// اختبار الدالة السابقة
	public static void main(String[] args) 
	{ 
		System.out.println(fact(5)); 
	} 
}

يمكن كتابة الدالة أعلاه بطريقة تجعلها دالة تعاودية مذيلة. يمكن استخدام معامل واحد أو أكثر وتجميع قيمة المضروب في المعامل الثاني، وعندما تصل قيمة n إلى 0، تعيد الدالة القيمة المجمّعة.

• C++‎:

#include<iostream> 
using namespace std; 

unsigned factTR(unsigned int n, unsigned int a) 
{ 
	if (n == 0) return a; 

	return factTR(n-1, n*a); 
} 

// facTR دالة تغليف للدالة 
unsigned int fact(unsigned int n) 
{ 
return factTR(n, 1); 
} 

// اختبار الدوال السابقة
int main() 
{ 
	cout << fact(5); 
	return 0; 
}

• بايثون:

def factTR(n, a): 

	if (n == 0): 
		return a 

	return factTR(n - 1, n * a) 

# facTR دالة تغليف للدالة  
def fact(n): 
	return factTR(n, 1) 

# اختبار الدالة السابقة 
print(fact(5))

• جافا:

class GFG { 
	
	static int factTR(int n, int a) 
	{ 
		if (n == 0) 
			return a; 
	
		return factTR(n - 1, n * a); 
	} 
	
	// factTR دالة تغليف للدالة
	static int fact(int n) 
	{ 
		return factTR(n, 1); 
	} 

	// اختبار الدالة السابقة
	static public void main (String[] args) 
	{ 
		System.out.println(fact(5)); 
	} 
}

حجز الذاكرة للدوال التعاودية

عند استدعاء الدالة من الدالة الرئيسية main()‎ يُحجز مقدار من الذاكرة في المكدس، وعندما تستدعي الدالة التعاودية نفسها يُحجز مقدار آخر من الذاكر فوق المقدار المحجوز أصلًا للدالة المستدعية وتُنشئ نسخة مختلفة من المتغيرات المحلية لكل استدعاء. وعند الوصول إلى الحالة الأساس، تعيد الدالة قيمتها إلى الدالة التي استدعتها، ويتم التخلص من الذاكرة المحجوزة وتستمر العملية.

أمثلة

تعرض الأمثلة التالية طريقة إنشاء الدوال التعاودية في عدد من لغات البرمجة:

#include<bits/stdc++.h> 
using namespace std; 

void printFun(int test) 
{ 
	if (test < 1) 
		return; 
	else
	{ 
		cout << test << " "; 
		printFun(test-1); // العبارة 2 
		cout << test << " "; 
		return; 
	} 
} 

int main() 
{ 
	int test = 3; 
	printFun(test); 
}

• بايثون:

def printFun(test): 

	if (test < 1): 
		return
	else: 
	
		print( test,end = " ") 
		printFun(test-1) # العبارة 2 
		print( test,end = " ") 
		return
	

test = 3
printFun(test)

• جافا:

class GFG{ 
static void printFun(int test) 
{ 
	if (test < 1) 
		return; 
	else
	{ 
		System.out.printf("%d ",test); 
		printFun(test-1); // العبارة 2 
		System.out.printf("%d ",test); 
		return; 
	} 
} 

public static void main(String[] args) 
{ 
	int test = 3; 
	printFun(test); 
} 
}

يُحجز مقدار من الذاكرة عند استدعاء الدالة printFun(3)‎ ويهيّئ المتغيّر المحلي test ليأخذ القيمة 3 ويضاف التعبيران 1 و 4 إلى المكدس، وتطبع الدالة القيمة 3 في البداية. في العبارة 2، تستدعى الدالة printFun(2)‎ ويحجز مقدار من الذاكرة لهذه الدالة ويهيئ المتغير المحلي testإلى القيمة 12 وتضاف العبارتان 1 و 4 إلى المكدس. وبنفس الطريقة تستدعي الدالة printFun(2)‎ الدالة printFun(1)‎ وتستدعي الأخيرة الدالة prinFun(0)‎.

تصل الدالة printFun(0)‎ في عملها إلى عبارة if الشرطية وتعود إلى الدالة printFun(1)‎ ثم تنفّذ بقية العبارات في الدالة printFun(1)‎ لتعود الدالة بعدها إلى الدالة printFun(2)‎ وهكذا. تطبع الدالة في المخرجات الأعداد من 3 إلى 1 ثم تطبع الأعداد 1 إلى 3.

مساوئ التعاود ومميزاته

يمكن حلّ المسائل بالطريقتين التكرارية iterative والتعاودية؛ بمعنى أنّه يمكن تحويل أي برنامج مكتوب بطريقة تعاودية إلى برنامج مكتوب بطريقة تكرارية، والعكس صحيح كذلك. ولكن البرنامج التعاودي يستهلك مساحة أكبر من البرنامج التكراري، وذلك لأنّ جميع الدوال ستبقى في المكدس إلى حين الوصول إلى الحالة الأساس. كذلك يتطلب البرنامج التعاودي زمنًا أطول في التنفيذ وذلك بسبب استدعاء الدالة مرة بعد أخرى ثم العودة إلى البداية من جديد.

ولكن تقدّم الطريقة التعاودية أسلوبًا بسيطًا وواضحًا لكتابة الشيفرة. تكون بعض المسائل مسائل تعاودية في الأصل، كما هو الحال في عملية التنقل عبر عناصر الشجرة tree traversal، وخوارزمية أبراج هانوي، وغيرها. ويُفضل استخدام الشيفرة التعاودية لحلّ مثل هذه المسائل. ويجدر التنبيه إلى أنّ بالإمكان حل هذه المسائل باستخدام الطريقة التكرارية وبالاستعانة بمكدس البيانات.

مسألة برج هانوي

خوارزمية برج هانوي Tower of Hanoi هي مسألة رياضية يستخدم فيها ثلاثة قضبان و عدد معين (ليكن n) من الأقراص، والهدف هو تحريك كدس الأقراص من قضيب إلى آخر  باتباع بعض القواعد المحددة.

إيجاد حاصل ضرب عددين دون استخدام العوامل الحسابية

المطلوب في هذه المسألة هو إيجاد حاصل ضرب عددين صحيحين دون استخدام عوامل الضرب والقسمة وعوامل الأعداد الثنائية ودون استخدام أي نوع من الحلقات التكرارية.

مصادر

• صفحة Recursion في توثيق الخوارزميات في موقع GeeksforGeeks.
• صفحة Tail Recursion في توثيق الخوارزميات في موقع GeeksforGeeks.