أمثلة على Recursion .. ” الاستدعاء الذاتي في هياكل البيانات “
ماهي تقنية الاستدعاء الذاتي Recursion
إن الوظائف التكرارية أو الاستدعاء الذاتي هي من
أنواع الخوارزميات البرمجية
حيث أنها في مصطلحات
البرمجة
تعرف الوظيفة العودية بأنها هي إجراء يستدعي نفسه بشكل مباشر أو بشكل غير مباشر، ويتم باستخدام الخوارزمية العودية أو الاستدعاء الذاتي، حيث أنه من الممكن أن يتم حل المشكلات بشكل سهل عن طريق الخوارزمية العودية أو الوظيفة التكرارية، وإن المعنى الحرفي لها هو الاستدعاء الذاتي فهي methods نقوم بنداء نفسها بنفسها، وإن لهذه ال method هيكلية خاصة بها وأساسيات.[2]
أمثلة على Recursion
إن للاستدعاء التكراري طرق مختلفة لكتابتها فهناك الطريقة المباشرة والطريقة الغير مباشرة، فسنتطرق إلى أبراج كود هانوي وهو من الأمثلة على الاتصال المباشر وسنتطرق إلى تنفيذه بعدة لغات:
أمثلة على الطريقة المباشرة بلغة++C
#include <bits/stdc++.h>
using
namespace
std;
// Assuming n-th disk is bottom disk (count down)
void
tower(
int
n,
char
sourcePole,
char
destinationPole,
char
auxiliaryPole)
{
// Base case (termination condition)
if
(0 == n)
return
;
// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
tower(n - 1, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
cout <<
"Move the disk "
<< n <<
" from "
<<
sourcePole <<
" to "
<< destinationPole << endl;
// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
tower(n - 1, auxiliaryPole, destinationPole,
sourcePole);
}
// Driver code
int
main()
{
tower(3,
'S'
,
'D'
,
'A'
);
return
0;
}
// This code is contributed by SHUBHAMSINGH10
أمثلة على الطريقة المباشرة بلغة الجافا
// Assuming n-th disk is
// bottom disk (count down)
class
GFG {
static
void
tower(
int
n,
char
sourcePole,
char
destinationPole,
char
auxiliaryPole)
{
// Base case (termination condition)
if
(
0
== n)
return
;
// Move first n-1 disks from source pole
// to auxiliary pole using destination as
// temporary pole
tower(n -
1
, sourcePole, auxiliaryPole,
destinationPole);
// Move the remaining disk from source
// pole to destination pole
System.out.printf(
"Move the disk %d from %c to %cn"
,
n, sourcePole, destinationPole);
// Move the n-1 disks from auxiliary (now source)
// pole to destination pole using source pole as
// temporary (auxiliary) pole
tower(n -
1
, auxiliaryPole, destinationPole, sourcePole);
}
public
static
void
main(String[] args)
{
tower(
3
,
'S'
,
'D'
,
'A'
);
}
}
// This code is contributed by Smitha Dinesh Semwal.
أمثلة على الطريقة المباشرة بلغة البايثون 3
# Assuming n-th disk is
# bottom disk (count down)
def
tower(n, sourcePole, destinationPole, auxiliaryPole):
# Base case (termination condition)
if
(
0
=
=
n):
return
# Move first n-1 disks
# from source pole
# to auxiliary pole
# using destination as
# temporary pole
tower(n
-
1
, sourcePole, auxiliaryPole, destinationPole)
# Move the remaining
# disk from source
# pole to destination pole
print
(
"Move the disk"
,sourcePole,
"from"
,sourcePole,
"to"
,destinationPole)
# Move the n-1 disks from
# auxiliary (now source)
# pole to destination pole
# using source pole as
# temporary (auxiliary) pole
tower(n
-
1
, auxiliaryPole, destinationPole,sourcePole)
# Driver code
[2]tower(
3
,
'S'
,
'D'
,
'A'
)
ومن الأمثلة على الاستدعاء الذاتي طباعة الأعداد:
الأرقام
من س إلى الرقم 1 بشكل تنازلي، ويكون البرنامج كالتالي:
public
void
printInt
(
int
i
)
{
if
(
i
==
1
){
.
out
.
println
(
1
)
}
else
{
.
out
.
println
(
i
)
;printInt
(
i
–
1
)
{public
void
printInt
(
int
i
)
}if
(
i
==
1
)
.
out
.
println
(
1
)
}
else
{
;printInt
(
i
–
1
)
;
System
.
out
.
println
(
i
)
ومن الأمثلة على الاستدعاء الذاتي المجموع للعدد س:
}public
int
SUM
(
int
i
)
}if
(
i
==
0
)
;return
0
}
else
{
;
return
i
+
SUM
(
i
–
1
)
الاستدعاء الذاتي بلغة c
إن العملية التي تستدعي فيها الوظيفة نفسها تعرف باسم الوظيفة العودية وتسمى بالوظيفة المقابلة، ففي لغة ++c نفهم العودية أكثر عن طريق دالة عاملي والتي تتجلى في:[1]
f (n) = n * f (n-1) ، الشرط الأساسي: إذا كان n <= 1 ثم f (n) = 1.
فالغرض من العودية هو تقسيم المشكلة إلى مشاكل أصغر حتى تصل إلى الحالة الأساسية، ويتم عن طريق استدعاء دالة عاملية f(n).
أنواع تقنية الاستدعاء الذاتي
إن الاستدعاء الذاتي يتكون من نوعين ويعتمد إذا كانت الوظيفة تستدعي نفسها من داخل نفسها أو تعمل على استداعاء أكثر من وظيفة، وإن نوعي تقنية الاستدعاء الذاتي هما:
-الاستدعاء الذاتي المباشر
وتصنف إلى أربعة أنواع وتتجلى في:
-
استدعاء الذاتي الذيلي Tail Recursion
وفيها يتم استداع الدالة لنفسها، ويكون هذا الاستدعاء هو العبارة الأخيرة في الدالة، وبعد أن يتم هذا الاستدعاء لا تؤدي الدالة إلى شيء، وإن هذه الدالة يجب أن تقوم بمعالجة أو تقوم بتنفيذ أي عملية في وقت الاستدعاء. -
الاستدعاء الذاتي الرأسي Head Recursion
فعندما تستدعي الدالة نفسها حيث أن هذا الاستدعاء يكون العبارة الأولى في الدالة فإن هذا الاستدعاء يعرف باسم الاستدعاء الذاتي الرأسي، وفيه لا تتواجد أي عبارة أو عملية قبل أن يحصل الاستدعاء، ولا تحتاج الدالة إلى أن تقوم بمعالجة أو تنفيذ أي عملية عند
الوقت
الذي يتم فيه الاستدعاء، وإن جميع العمليات يتم تنفيذها وقت الارجاع. -
الاستدعاء الذاتي الشجري Tree Recursion
وفي هذا الاستدعاء يتم عن طريق استدعاء الدالة لنفسها لأكثر من مرة، فهي على عكس الاستدعاء الذاتي الخطي الذي يتم فيه استدعاء الدالة لنفسها مرة واحدة فقط. -
الاستدعاء الذاتي الخطي Linear Recursion
وهي الدالة التي تقوم من خلال إجراء استدعاء واحد فقط لنفسها، ويتم هذا الاستدعاء في كل مرة يتم فيها تشغيل الدالة.
-الاستدعاء الذاتي الغير مباشر
ويتم في الاستدعاء الذاتي الغير مباشر اتصال أكثر من دالة ببعضهم البعض بشكل دائري، فهو استدعاء إحدى الوظائف نفسها بالشكل الغير مباشر من وظيفة أخرى.[3]
مزايا وخصائص الاستدعاء الذاتي
إن خصائص الاستدعاء الذاتي تتجلى في:
- أن الوظيفة التكرارية أو الاستدعاء الذاتي هي وظيفة تقوم على استدعاء نفسها.
- إن سرعة الاستدعاء الذاتي تكون أبطأ بسبب الأعباء المكدسة.
- إن وظيفة الاستدعاء الذاتي يجب أن تحتوي على شروط إنهاء أو حالة أساسية بالإضافة إلى احتوائها لتعبيرات متكررة.
بينما مزايا الاستدعاء الذاتي تتجلى في:
- إنه يجعل البرنامج نظيفاً.
- يعمل على تقصير التعليمات البرمجية المعقدة والمتداخلة.
بينما مساوئ الاستدعاء الذاتي تتجلى في :
- من الصعب أن يتم تصحيح الأخطاء.
- من الصعب أن يتم فهم المنطق.[4]