طريقة للانتقال من العودية إلى التكرار
https://stackoverflow.com/questions/159590
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لقد استخدمت التكرار كثيرًا خلال سنوات دراستي العديدة في البرمجة لحل المشكلات البسيطة، لكنني أدرك تمامًا أنك في بعض الأحيان تحتاج إلى التكرار بسبب مشاكل في الذاكرة/السرعة.
لذلك، في وقت ما في الماضي البعيد، ذهبت لمحاولة معرفة ما إذا كان هناك أي "نمط" أو طريقة كتاب نصي لتحويل نهج العودية الشائع إلى التكرار ولم أجد شيئًا.أو على الأقل لا شيء أستطيع أن أتذكره من شأنه أن يساعد.
- هل هناك قواعد عامة؟
- هل هناك "نمط"؟
المحلول
عادة، أقوم باستبدال الخوارزمية العودية بخوارزمية تكرارية عن طريق دفع المعلمات التي يتم تمريرها عادةً إلى الدالة العودية إلى المكدس.في الواقع، أنت تقوم باستبدال مكدس البرنامج بآخر خاص بك.
Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
// Do something
my_object = stack.pop();
// Push other objects on the stack.
}
ملحوظة:إذا كان لديك أكثر من مكالمة متكررة بالداخل وتريد الحفاظ على ترتيب المكالمات، فيجب عليك إضافتها بترتيب عكسي إلى المكدس:
foo(first);
foo(second);
يجب استبداله بـ
stack.push(second);
stack.push(first);
يحرر:المقالة الأكوام والقضاء على العودية (أو رابط المادة الاحتياطية) يدخل في مزيد من التفاصيل حول هذا الموضوع.
نصائح أخرى
حقًا، الطريقة الأكثر شيوعًا للقيام بذلك هي الاحتفاظ بالمكدس الخاص بك.فيما يلي وظيفة الفرز السريع العودية في لغة C:
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
إليك كيف يمكننا أن نجعلها متكررة من خلال الاحتفاظ بالمكدس الخاص بنا:
void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
من الواضح أن هذا المثال لا يتحقق من حدود المكدس ...ويمكنك بالفعل تغيير حجم المكدس بناءً على أسوأ الحالات المعطاة للقيم اليسرى واليمنى.لكن انت فهمت الفكرة.
يبدو أنه لم يتناول أحد المكان الذي تستدعي فيه الدالة العودية نفسها أكثر من مرة في الجسم، وتتعامل مع العودة إلى نقطة معينة في العودية (أي:ليست بدائية العودية).ويقال أن يمكن تحويل كل العودية إلى التكرار, ، لذلك يبدو أن هذا يجب أن يكون ممكنا.
لقد توصلت للتو إلى مثال C# لكيفية القيام بذلك.لنفترض أن لديك الدالة العودية التالية، والتي تعمل مثل اجتياز الطلب اللاحق، وأن AbcTreeNode عبارة عن شجرة ثلاثية ذات مؤشرات a، b، c.
public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
if (x != null) {
AbcRecursiveTraversal(x.a, list);
AbcRecursiveTraversal(x.b, list);
AbcRecursiveTraversal(x.c, list);
list.Add(x.key);//finally visit root
}
}
الحل التكراري:
int? address = null;
AbcTreeNode x = null;
x = root;
address = A;
stack.Push(x);
stack.Push(null)
while (stack.Count > 0) {
bool @return = x == null;
if (@return == false) {
switch (address) {
case A://
stack.Push(x);
stack.Push(B);
x = x.a;
address = A;
break;
case B:
stack.Push(x);
stack.Push(C);
x = x.b;
address = A;
break;
case C:
stack.Push(x);
stack.Push(null);
x = x.c;
address = A;
break;
case null:
list_iterative.Add(x.key);
@return = true;
break;
}
}
if (@return == true) {
address = (int?)stack.Pop();
x = (AbcTreeNode)stack.Pop();
}
}
نسعى جاهدين لإجراء مكالمتك العودية العودية الذيل (العودية حيث العبارة الأخيرة هي المكالمة العودية).بمجرد حصولك على ذلك، يصبح تحويله إلى التكرار أمرًا سهلاً بشكل عام.
حسنًا، بشكل عام، يمكن محاكاة التكرار كتكرار ببساطة عن طريق استخدام متغير تخزين.لاحظ أن العودية والتكرار متكافئان بشكل عام؛يمكن دائمًا تحويل أحدهما إلى الآخر.من السهل جدًا تحويل الدالة العودية إلى وظيفة تكرارية.ما عليك سوى جعل المتغير التراكمي متغيرًا محليًا، ثم تكراره بدلاً من التكرار.فيما يلي مثال في لغة C++ (لغة C لولا استخدام الوسيطة الافتراضية):
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
من خلال معرفتي، من المحتمل أنني ارتكبت خطأً في الكود، لكن الفكرة موجودة.
حتى استخدام المكدس لن يحول الخوارزمية العودية إلى خوارزمية تكرارية.العودية العادية هي العودية القائمة على الوظيفة وإذا استخدمنا المكدس فإنها تصبح العودية القائمة على المكدس.ولكن لا يزال العودية.
بالنسبة للخوارزميات العودية، يكون التعقيد المكاني هو O(N) والتعقيد الزمني هو O(N).بالنسبة للخوارزميات التكرارية، يكون التعقيد المكاني هو O(1) والتعقيد الزمني هو O(N).
ولكن إذا استخدمنا الأشياء المكدسة من حيث التعقيد يظل كما هو.أعتقد أن التكرار الذيل فقط هو الذي يمكن تحويله إلى تكرار.
ال المداخن والقضاء على العودية تلتقط المقالة فكرة إضفاء الطابع الخارجي على إطار المكدس على الكومة، ولكنها لا توفر واضحة وقابلة للتكرار طريقة للتحويل.أدناه واحد.
أثناء التحويل إلى تعليمات برمجية تكرارية، يجب على المرء أن يدرك أن الاستدعاء العودي قد يحدث من كتلة تعليمات برمجية عميقة بشكل تعسفي.لا يقتصر الأمر على المعلمات فحسب، بل أيضًا نقطة العودة إلى المنطق الذي لا يزال يتعين تنفيذه وحالة المتغيرات التي تشارك في الشروط الشرطية اللاحقة، وهو أمر مهم.فيما يلي طريقة بسيطة جدًا للتحويل إلى تعليمات برمجية تكرارية بأقل قدر من التغييرات.
النظر في هذا الرمز العودي:
struct tnode
{
tnode(int n) : data(n), left(0), right(0) {}
tnode *left, *right;
int data;
};
void insertnode_recur(tnode *node, int num)
{
if(node->data <= num)
{
if(node->right == NULL)
node->right = new tnode(num);
else
insertnode(node->right, num);
}
else
{
if(node->left == NULL)
node->left = new tnode(num);
else
insertnode(node->left, num);
}
}
الكود التكراري:
// Identify the stack variables that need to be preserved across stack
// invocations, that is, across iterations and wrap them in an object
struct stackitem
{
stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
tnode *node; int num;
int ra; //to point of return
};
void insertnode_iter(tnode *node, int num)
{
vector<stackitem> v;
//pushing a stackitem is equivalent to making a recursive call.
v.push_back(stackitem(node, num));
while(v.size())
{
// taking a modifiable reference to the stack item makes prepending
// 'si.' to auto variables in recursive logic suffice
// e.g., instead of num, replace with si.num.
stackitem &si = v.back();
switch(si.ra)
{
// this jump simulates resuming execution after return from recursive
// call
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
// replace a recursive call with below statements
// (a) save return point,
// (b) push stack item with new stackitem,
// (c) continue statement to make loop pick up and start
// processing new stack item,
// (d) a return point label
// (e) optional semi-colon, if resume point is an end
// of a block.
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
}
}
v.pop_back();
}
}
لاحظ كيف أن بنية الكود لا تزال مطابقة للمنطق العودي وأن التعديلات ضئيلة، مما يؤدي إلى تقليل عدد الأخطاء.للمقارنة، قمت بتمييز التغييرات بـ ++ و-.معظم الكتل الجديدة المدرجة باستثناء v.push_back، شائعة في أي منطق تكراري محول
void insertnode_iter(tnode *node, int num)
{
+++++++++++++++++++++++++
vector<stackitem> v;
v.push_back(stackitem(node, num));
while(v.size())
{
stackitem &si = v.back();
switch(si.ra)
{
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
------------------------
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
-------------------------
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
-------------------------
}
}
+++++++++++++++++++++++++
v.pop_back();
}
-------------------------
}
ابحث عن Google عن "نمط تمرير الاستمرار". هناك إجراء عام للتحويل إلى نمط عودية ذيل ؛هناك أيضًا إجراء عام لتحويل الوظائف العودية الخلفية إلى حلقات.
فقط قتل الوقت...وظيفة العودية
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
يمكن تحويلها إلى
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
stack.push(node->right);
stack.push(node->left);
while(!stack.empty()) {
node1 = stack.pop();
if(node1 == NULL)
continue;
// Do something with node1...
stack.push(node1->right);
stack.push(node1->left);
}
}
بشكل عام، تسمى تقنية تجنب تجاوز سعة المكدس للوظائف العودية تقنية الترامبولين والتي يتم اعتمادها على نطاق واسع بواسطة مطوري Java.
ومع ذلك، بالنسبة لـ C#، هناك طريقة مساعدة صغيرة هنا الذي يحول وظيفتك العودية إلى وظيفة تكرارية دون الحاجة إلى تغيير المنطق أو جعل الكود غير مفهوم.لغة C# هي لغة جميلة يمكن معها تحقيق أشياء مذهلة.
يعمل عن طريق تغليف أجزاء من الطريقة بطريقة مساعدة.على سبيل المثال الدالة العودية التالية:
int Sum(int index, int[] array)
{
//This is the termination condition
if (int >= array.Length)
//This is the returning value when termination condition is true
return 0;
//This is the recursive call
var sumofrest = Sum(index+1, array);
//This is the work to do with the current item and the
//result of recursive call
return array[index]+sumofrest;
}
تحول الى:
int Sum(int[] ar)
{
return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
التفكير في الأشياء التي تحتاج بالفعل إلى مكدس:
إذا اعتبرنا نمط التكرار على النحو التالي:
if(task can be done directly) {
return result of doing task directly
} else {
split task into two or more parts
solve for each part (possibly by recursing)
return result constructed by combining these solutions
}
على سبيل المثال، برج هانوي الكلاسيكي
if(the number of discs to move is 1) {
just move it
} else {
move n-1 discs to the spare peg
move the remaining disc to the target peg
move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}
يمكن ترجمة ذلك إلى حلقة تعمل على مكدس صريح، من خلال إعادة صياغتها على النحو التالي:
place seed task on stack
while stack is not empty
take a task off the stack
if(task can be done directly) {
Do it
} else {
Split task into two or more parts
Place task to consolidate results on stack
Place each task on stack
}
}
بالنسبة لبرج هانوي يصبح هذا:
stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
task = stack.pop();
if(task.size() = 1) {
just move it
} else {
stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
stack.push(new Task(1, task.from(), task.to(), task.spare()));
stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
}
}
هناك قدر كبير من المرونة هنا فيما يتعلق بكيفية تعريف مجموعتك.يمكنك جعل مجموعتك قائمة بـ Command الأشياء التي تفعل أشياء معقدة.أو يمكنك السير في الاتجاه المعاكس وجعله قائمة بالأنواع الأبسط (على سبيل المثال.قد تكون "المهمة" عبارة عن 4 عناصر في مجموعة من العناصر int, ، بدلاً من عنصر واحد في كومة من Task).
كل هذا يعني أن ذاكرة المكدس موجودة في الكومة وليس في مكدس تنفيذ Java، ولكن يمكن أن يكون هذا مفيدًا حيث يمكنك التحكم فيه بشكل أكبر.
أحد الأنماط التي يجب البحث عنها هو استدعاء العودية في نهاية الوظيفة (ما يسمى العودية الخلفية).يمكن بسهولة استبدال هذا مع بعض الوقت.على سبيل المثال، الدالة foo:
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
ينتهي بمكالمة foo.يمكن استبدال هذا بـ:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
مما يلغي المكالمة العودية الثانية.
لقد قمت للتو بالتصويت على الإجابة التي تقترح استخدام مكدس صريح أعتقد أنه الحل الصحيح وقابل للتطبيق بشكل عام.
أعني أنه يمكنك استخدامه لتحويل أي وظيفة عودية إلى وظيفة تكرارية.ما عليك سوى التحقق من القيم التي يتم حفظها عبر الاستدعاءات المتكررة، وتلك هي القيم التي يتم حفظها يملك لتكون محلية للوظيفة العودية، واستبدل الاستدعاءات بدورة حيث ستدفعها على المكدس.عندما تكون المكدس فارغة، سيتم إنهاء الوظيفة العودية.
لا أستطيع مقاومة القول إن الدليل على أن كل دالة عودية تعادل دالة تكرارية في نوع بيانات مختلف، إنها واحدة من أعز ذكرياتي في أوقات دراستي الجامعية.كانت تلك الدورة (والأستاذ) هي التي جعلتني أفهم حقًا موضوع برمجة الكمبيوتر.
أ سؤال التي تم إغلاقها كنسخة مكررة من هذه تحتوي على بنية بيانات محددة للغاية:
كان للعقدة الهيكل التالي:
typedef struct {
int32_t type;
int32_t valueint;
double valuedouble;
struct cNODE *next;
struct cNODE *prev;
struct cNODE *child;
} cNODE;
تبدو وظيفة الحذف العودية كما يلي:
void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
بشكل عام، ليس من الممكن دائمًا تجنب مكدس الوظائف العودية التي تستدعي نفسها أكثر من مرة (أو حتى مرة واحدة).ومع ذلك، بالنسبة لهذا الهيكل بالذات، فمن الممكن.والفكرة هي لتسوية كافة العقد في قائمة واحدة.يتم تحقيق ذلك عن طريق وضع العقدة الحالية child في نهاية قائمة الصف العلوي.
void cNODE_Delete (cNODE *c) {
cNODE *tmp, *last = c;
while (c) {
while (last->next) {
last = last->next; /* find last */
}
if ((tmp = c->child)) {
c->child = NULL; /* append child to last */
last->next = tmp;
tmp->prev = last;
}
tmp = c->next; /* remove current */
free(c);
c = tmp;
}
}
يمكن تطبيق هذه التقنية على أي بنية مرتبطة بالبيانات والتي يمكن اختزالها إلى DAG بترتيب طوبولوجي محدد.تتم إعادة ترتيب أطفال العقد الحالية بحيث يتبنى الطفل الأخير جميع الأطفال الآخرين.بعد ذلك يمكن حذف العقدة الحالية ويمكن بعد ذلك تكرار الاجتياز إلى العقدة الفرعية المتبقية.
العودية ليست سوى عملية استدعاء دالة من أخرى فقط هذه العملية تتم عن طريق استدعاء دالة بنفسها.كما نعلم أنه عندما تستدعي إحدى الوظائف الوظيفة الأخرى، فإن الوظيفة الأولى تحفظ حالتها (متغيراتها) ثم تمرر التحكم إلى الوظيفة المطلوبة.يمكن استدعاء الدالة المستدعىة باستخدام نفس اسم المتغيرات، على سبيل المثال يمكن لـ fun1(a) استدعاء fun2(a).عندما نقوم بإجراء مكالمة متكررة، لا يحدث شيء جديد.تستدعي إحدى الوظائف نفسها عن طريق تمرير نفس النوع ومتغيرات مشابهة في الاسم (ولكن من الواضح أن القيم المخزنة في المتغيرات مختلفة، ويبقى الاسم فقط كما هو.) لنفسها.ولكن قبل كل مكالمة، تقوم الوظيفة بحفظ حالتها وتستمر عملية الحفظ هذه.يتم التوفير على كومة.
الآن يأتي دور المكدس.
لذا، إذا كتبت برنامجًا تكراريًا وحفظت الحالة على المكدس في كل مرة ثم أخرجت القيم من المكدس عند الحاجة، فقد نجحت في تحويل برنامج عودي إلى برنامج تكراري!
والدليل بسيط وتحليلي.
في العودية يحتفظ الكمبيوتر بمكدس وفي الإصدار التكراري سيتعين عليك صيانة المكدس يدويًا.
فكر في الأمر، ما عليك سوى تحويل برنامج متكرر للبحث العميق (على الرسوم البيانية) إلى برنامج تكراري dfs.
أتمنى لك كل خير!
وصف تقريبي لكيفية قيام النظام بأي وظيفة متكررة وتنفيذها باستخدام المكدس:
وهذا يهدف إلى إظهار الفكرة دون تفاصيل.خذ بعين الاعتبار هذه الوظيفة التي من شأنها طباعة عقد الرسم البياني:
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
على سبيل المثال الرسم البياني:A-> b a-> c show (a) سوف يطبع b ، a ، c
تعني استدعاءات الوظائف حفظ الحالة المحلية ونقطة الاستمرار حتى تتمكن من العودة، ثم الانتقال إلى الوظيفة التي تريد الاتصال بها.
على سبيل المثال، لنفترض أن العرض (A) يبدأ في التشغيل.استدعاء الوظيفة على السطر 3.إظهار (ب) يعني - إضافة عنصر إلى المعنى المكدس "ستحتاج إلى المتابعة في السطر 2 مع Node State State المحلي = A" - GOTO LINE 0 مع Node = B.
لتنفيذ التعليمات البرمجية، يعمل النظام من خلال التعليمات.عند مواجهة استدعاء دالة، يدفع النظام المعلومات التي يحتاجها للعودة إلى حيث كانت، ويقوم بتشغيل رمز الوظيفة، وعندما تكتمل الوظيفة، يُظهر المعلومات حول المكان الذي يجب أن تذهب إليه للمتابعة.
هذا وصلة يقدم بعض الشرح ويقترح فكرة الاحتفاظ بـ "الموقع" لتتمكن من الوصول إلى المكان المحدد بين عدة مكالمات متكررة:
ومع ذلك، تصف كافة هذه الأمثلة السيناريوهات التي يتم فيها إجراء استدعاء متكرر مُثَبَّت كمية من المرات.تصبح الأمور أكثر تعقيدًا عندما يكون لديك شيء مثل:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
هناك طريقة عامة لتحويل الاجتياز العودي إلى مكرر باستخدام مكرر كسول يقوم بتسلسل موردي مكرر متعددين (تعبير لامدا الذي يُرجع مكررًا).انظر بلدي تحويل الاجتياز العودي إلى التكرار.
مثال آخر بسيط وكامل لتحويل الدالة العودية إلى دالة تكرارية باستخدام المكدس.
#include <iostream>
#include <stack>
using namespace std;
int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
struct Par
{
int a, b;
Par() : Par(0, 0) {}
Par(int _a, int _b) : a(_a), b(_b) {}
};
int GCDIter(int a, int b)
{
stack<Par> rcstack;
if (b == 0)
return a;
rcstack.push(Par(b, a % b));
Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}
return p.a;
}
int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;
cin.get();
return 0;
}
