ما هو العودية الذيل؟

Question

عندما بدأت في تعلم اللثغة، صادفت هذا المصطلح الذيل العودي.ماذا تعني بالتحديد؟

Answer 1

فكر في دالة بسيطة تجمع الأعداد الصحيحة N الأولى.(على سبيل المثال sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

فيما يلي تطبيق JavaScript بسيط يستخدم التكرار:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

إذا اتصلت recsum(5), هذا ما سيقيمه مترجم JavaScript:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

لاحظ كيف يجب أن تكتمل كل مكالمة متكررة قبل أن يبدأ مترجم JavaScript في القيام فعليًا بعمل حساب المجموع.

إليك نسخة متكررة من نفس الوظيفة:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

إليك تسلسل الأحداث التي قد تحدث إذا اتصلت tailrecsum(5), ، (والذي سيكون فعالا tailrecsum(5, 0), ، بسبب الوسيطة الثانية الافتراضية).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

في حالة الذيل العودي، مع كل تقييم للاستدعاء العودي، فإن running_total يتم تحديث.

ملحوظة:استخدمت الإجابة الأصلية أمثلة من بايثون.لقد تم تغييرها إلى JavaScript، نظرًا لدعم مترجمي JavaScript الفوريين تحسين المكالمة الذيل لكن مترجمي بايثون لا يفعلون ذلك.

Answer 2

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

في العودية الذيل, ، تقوم بإجراء حساباتك أولاً، ثم تقوم بتنفيذ الاستدعاء العودي، وتمرير نتائج خطوتك الحالية إلى الخطوة العودية التالية.وينتج عن هذا أن يكون البيان الأخير على شكل (return (recursive-function params)). في الأساس، قيمة الإرجاع لأي خطوة عودية معينة هي نفس قيمة الإرجاع للاستدعاء التكراري التالي.

والنتيجة هي أنه بمجرد أن تصبح جاهزًا لتنفيذ خطوتك العودية التالية، فلن تحتاج إلى إطار المكدس الحالي بعد الآن.وهذا يسمح لبعض التحسين.في الواقع، مع وجود مترجم مكتوب بشكل مناسب، يجب ألا يكون لديك تجاوز سعة المكدس أبدًا حمحم مع مكالمة متكررة الذيل.ما عليك سوى إعادة استخدام إطار المكدس الحالي للخطوة العودية التالية.أنا متأكد من أن Lisp يفعل هذا.

Answer 3

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

while(E) { S }; return Q

أين E و Q هي التعبيرات و S عبارة عن سلسلة من البيانات، وتحويلها إلى وظيفة متكررة

f() = if E then { S; return f() } else { return Q }

بالطبع، E, S, ، و Q يجب تعريفها لحساب بعض القيمة المثيرة للاهتمام على بعض المتغيرات.على سبيل المثال، وظيفة التكرار

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

يعادل وظيفة (وظائف) الذيل العودية

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(هذا "الالتفاف" للدالة العودية الخلفية مع دالة ذات معلمات أقل هو مصطلح وظيفي شائع.)

Answer 4

هذا مقتطف من الكتاب البرمجة في لوا عروض كيفية جعل العودية الذيل السليم (في Lua، ولكن يجب أن ينطبق على Lisp أيضًا) ولماذا هو أفضل.

أ مكالمة الذيل عودة الذيل] هو نوع من غوتو يرتديها كمكالمة.تحدث مكالمة الذيل عندما تستدعي دالة أخرى كإجراء آخر ، لذلك ليس لديها أي شيء آخر.على سبيل المثال ، في الكود التالي ، المكالمة إلى g هو نداء الذيل:

function f (x)
  return g(x)
end

بعد f المكالمات g, ، لا يوجد شيء آخر.في مثل هذه الحالات ، لا يحتاج البرنامج إلى العودة إلى وظيفة الاتصال عندما تنتهي الوظيفة المستدعية.لذلك ، بعد مكالمة الذيل ، لا يحتاج البرنامج إلى الاحتفاظ بأي معلومات حول وظيفة الاتصال في المكدس....

نظرًا لأن مكالمة الذيل المناسبة لا تستخدم مساحة المكدس ، فلا يوجد حد لعدد مكالمات الذيل "المتداخلة" التي يمكن للبرنامج إجراءها.على سبيل المثال ، يمكننا استدعاء الوظيفة التالية مع أي رقم كوسيطة ؛لن تتفوق على المكدس أبدًا:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

...كما قلت سابقًا ، فإن مكالمة الذيل هي نوع من goto.على هذا النحو ، فإن تطبيقًا مفيدًا جدًا لمكالمات الذيل المناسبة في LUA هو لآلات الدولة للبرمجة.يمكن أن تمثل هذه التطبيقات كل ولاية من خلال وظيفة ؛لتغيير الحالة هو الذهاب إلى (أو الاتصال) وظيفة محددة.على سبيل المثال ، دعونا نفكر في لعبة متاهة بسيطة.تتميز المتاهة بعدة غرف ، لكل منها ما يصل إلى أربعة أبواب:الشمال والجنوب والشرق والغرب.في كل خطوة ، يدخل المستخدم اتجاه الحركة.إذا كان هناك باب في هذا الاتجاه ، يذهب المستخدم إلى الغرفة المقابلة ؛خلاف ذلك ، يطبع البرنامج تحذيرًا.الهدف هو الانتقال من غرفة أولية إلى غرفة أخيرة.

هذه اللعبة هي آلة حالة نموذجية ، حيث الغرفة الحالية هي الدولة.يمكننا تنفيذ هذه المتاهة مع وظيفة واحدة لكل غرفة.نستخدم مكالمات الذيل للانتقال من غرفة إلى أخرى.يمكن أن تبدو متاهة صغيرة مع أربع غرف هكذا:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

كما ترى، عند إجراء مكالمة متكررة مثل:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

هذا ليس تكرارًا خلفيًا لأنه لا يزال لديك أشياء للقيام بها (أضف 1) في هذه الوظيفة بعد إجراء المكالمة العودية.إذا قمت بإدخال رقم كبير جدًا، فمن المحتمل أن يتسبب ذلك في تجاوز سعة المكدس.

Answer 5

باستخدام العودية العادية، تقوم كل مكالمة متكررة بدفع إدخال آخر إلى مكدس الاستدعاءات.عند اكتمال عملية التكرار، يجب على التطبيق بعد ذلك أن يقوم بإخراج كل إدخال إلى الأسفل.

باستخدام التكرار الخلفي، اعتمادًا على اللغة، قد يكون المترجم قادرًا على طي المكدس إلى إدخال واحد، لذلك يمكنك توفير مساحة المكدس...يمكن أن يتسبب الاستعلام التكراري الكبير في تجاوز سعة المكدس.

بشكل أساسي، يمكن تحسين العودية الخلفية في التكرار.

Answer 6

بدلاً من شرح ذلك بالكلمات، إليك مثالاً.هذه نسخة مخططة من دالة المضروب:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

فيما يلي نسخة من العامل الذي يكون متكررًا:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

ستلاحظ في الإصدار الأول أن الاستدعاء العودي للحقيقة يتم إدخاله في تعبير الضرب، وبالتالي يجب حفظ الحالة على المكدس عند إجراء الاستدعاء العودي.في الإصدار العودي، لا يوجد تعبير S آخر ينتظر قيمة الاستدعاء العودي، وبما أنه لا يوجد عمل آخر للقيام به، فلا يلزم حفظ الحالة على المكدس.كقاعدة عامة، تستخدم الوظائف العودية للمخطط مساحة مكدس ثابتة.

Answer 7

يحتوي ملف المصطلحات على ما يقوله حول تعريف العودية الخلفية:

العودية الذيل /ن./

إذا لم تكن قد سئمت منه بالفعل، راجع التكرار الذيل.

Answer 8

يشير العودية الخلفية إلى أن المكالمة العودية هي الأخيرة في آخر تعليمات منطقية في الخوارزمية العودية.

عادة في العودية، لديك الحالة الأساسية وهو ما يوقف المكالمات العودية ويبدأ في ظهور مكدس الاستدعاءات.لاستخدام مثال كلاسيكي، على الرغم من أنه أكثر C-ish من Lisp، توضح الدالة المضروب التكرار الخلفي.تحدث المكالمة العودية بعد التحقق من حالة الحالة الأساسية.

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

سيكون الاستدعاء الأولي للمضروب factorial(n) أين fac=1 (القيمة الافتراضية) وn هو الرقم الذي سيتم حساب المضروب له.

Answer 9

ويعني ذلك أنه بدلاً من الحاجة إلى الضغط على مؤشر التعليمات على المكدس، يمكنك ببساطة الانتقال إلى أعلى الدالة العودية ومتابعة التنفيذ.يسمح هذا للوظائف بالتكرار إلى أجل غير مسمى دون تجاوز حجم المكدس.

كتبت أ مدونة نشر حول هذا الموضوع، والذي يحتوي على أمثلة رسومية لما تبدو عليه إطارات المكدس.

Answer 10

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

بسيطة جدا وبديهية لفهم.

هناك طريقة سهلة لمعرفة ما إذا كانت الدالة العودية هي دالة عودية ذيلية وهي إذا قامت بإرجاع قيمة محددة في الحالة الأساسية.بمعنى أنه لا يُرجع 1 أو صحيحًا أو أي شيء من هذا القبيل.من المرجح أن يُرجع نوعًا ما من أحد معلمات الطريقة.

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

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

Answer 11

أفضل طريقة بالنسبة لي لفهم tail call recursion هي حالة خاصة من العودية حيث آخر مكالمة(أو المكالمة الخلفية) هي الوظيفة نفسها.

مقارنة الأمثلة المتوفرة في بايثون:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^ العودية

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^ عودة الذيل

كما ترون في النسخة العودية العامة، فإن المكالمة النهائية في كتلة التعليمات البرمجية هي x + recsum(x - 1).لذلك بعد الاتصال بـ recsum طريقة، هناك عملية أخرى وهي x + ...

ومع ذلك، في النسخة العودية الخلفية، يكون النداء الأخير (أو النداء الخلفي) في كتلة التعليمات البرمجية هو tailrecsum(x - 1, running_total + x) مما يعني أنه تم إجراء آخر استدعاء للطريقة نفسها ولا توجد عملية بعد ذلك.

هذه النقطة مهمة لأن التكرار الخلفي كما هو موضح هنا لا يجعل الذاكرة تنمو لأنه عندما يرى الجهاز الظاهري الأساسي وظيفة تستدعي نفسها في موضع ذيل (آخر تعبير يتم تقييمه في دالة)، فإنه يلغي إطار المكدس الحالي، والذي يُعرف باسم تحسين المكالمات الخلفية (TCO).

يحرر

ملحوظة:ضع في اعتبارك أن المثال أعلاه مكتوب بلغة Python التي لا يدعم وقت تشغيلها التكلفة الإجمالية للملكية.وهذا مجرد مثال لتوضيح هذه النقطة.يتم دعم التكلفة الإجمالية للملكية بلغات مثل Scheme وHaskell وما إلى ذلك

Answer 12

في Java، إليك تطبيق عودي محتمل لدالة فيبوناتشي:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

قارن هذا مع التنفيذ العودي القياسي:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

Answer 13

فيما يلي مثال لـ Common Lisp الذي يقوم بإجراء المضروبات باستخدام التكرار الخلفي.نظرًا لطبيعة عدم وجود مكدس، يمكن للمرء إجراء حسابات عاملية كبيرة بجنون ...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

وبعد ذلك يمكنك المحاولة من أجل المتعة (format nil "~R" (! 25))

Answer 14

أنا لست مبرمج Lisp، ولكن أعتقد هذا سوف يساعد.

إنه في الأساس أسلوب برمجة بحيث تكون المكالمة العودية هي آخر شيء تفعله.

Answer 15

باختصار، العودية الذيلية لها استدعاء عودي باسم آخر عبارة في الوظيفة بحيث لا تضطر إلى انتظار المكالمة العودية.

لذلك هذا هو العودية الذيل أي.N(x - 1, p * x) هو البيان الأخير في الوظيفة حيث يكون المترجم ذكيًا في معرفة أنه يمكن تحسينه إلى حلقة for (مضروب).تحمل المعلمة الثانية p قيمة المنتج الوسيطة.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

هذه هي الطريقة غير العودية لكتابة دالة العوامل المذكورة أعلاه (على الرغم من أن بعض مترجمي C++ قد يكونون قادرين على تحسينها على أي حال).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

ولكن هذا ليس:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

لقد كتبت مقالة طويلة بعنوان "فهم العودية الخلفية – Visual Studio C++ – عرض التجميع"

Answer 16

هنا نسخة بيرل 5 من tailrecsum الوظيفة المذكورة سابقًا.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Answer 17

هذا مقتطف من هيكل وتفسير برامج الكمبيوتر حول العودية الذيل.

في التناقض مع التكرار والتكرار ، يجب أن نكون حريصين على عدم الخلط بين فكرة العملية العودية مع فكرة الإجراء العودية.عندما نصف الإجراء بأنه عودية ، فإننا نشير إلى الحقيقة النحوية المتمثلة في أن تعريف الإجراء يشير (إما بشكل مباشر أو غير مباشر) إلى الإجراء نفسه.ولكن عندما نصف عملية على أنها تتبع نمطًا ، على سبيل المثال ، متكرر خطيًا ، فإننا نتحدث عن كيفية تطور العملية ، وليس حول بناء جملة كيفية كتابة الإجراء.قد يبدو من المثير للقلق أننا نشير إلى إجراء عودية مثل FACT-Biter كإنشاء عملية تكرارية.ومع ذلك، فإن العملية تكرارية حقًا:يتم التقاط حالتها بالكامل من خلال متغيرات الدولة الثلاثة ، ويحتاج المترجم المترجم إلى تتبع ثلاثة متغيرات فقط من أجل تنفيذ العملية.

أحد الأسباب التي تجعل التمييز بين العملية والإجراءات أمرًا مربكًا هو أن معظم تطبيقات اللغات الشائعة (بما في ذلك ADA و Pascal و C) تم تصميمها بطريقة تجعل تفسير أي إجراء عودية يستهلك كمية من الذاكرة التي تنمو مع عدد مكالمات الإجراءات ، حتى عندما تكون العملية الموصوفة ، من حيث المبدأ ، تكرارية.نتيجة لذلك ، يمكن لهذه اللغات أن تصف العمليات التكرارية فقط من خلال اللجوء إلى "بنيات الحلقات" الخاصة بالأغراض الخاصة مثل DO ، كرر ، حتى ، و ". لا يشارك تنفيذ المخطط هذا العيب.سيتم تنفيذ عملية تكرارية في مساحة ثابتة ، حتى لو تم وصف العملية التكرارية بإجراء عودية.يسمى التنفيذ مع هذه الخاصية. من خلال تطبيق خلفي الذيل ، يمكن التعبير عن التكرار باستخدام آلية استدعاء الإجراء العادية ، بحيث تكون بنيات التكرار الخاصة مفيدة فقط كسكر النحوي.

Answer 18

العودية الذيلية هي الحياة التي تعيشها الآن.أنت تقوم باستمرار بإعادة تدوير نفس إطار المكدس، مرارًا وتكرارًا، لأنه لا يوجد سبب أو وسيلة للعودة إلى الإطار "السابق".لقد انتهى الماضي وانتهى حتى يمكن التخلص منه.تحصل على إطار واحد، ينتقل إلى المستقبل إلى الأبد، حتى تموت عمليتك حتماً.

_{ينهار التشبيه عندما تفكر في أن بعض العمليات قد تستخدم إطارات إضافية ولكنها لا تزال تعتبر متكررة إذا لم تنمو المكدس بشكل لا نهائي.}

Answer 19

إن عودة الذيل هو وظيفة متكررة حيث تستدعي الوظيفة نفسها في النهاية ("الذيل") للوظيفة التي لا يتم فيها أي حساب بعد عودة المكالمة العودية.يعمل العديد من المترجمين على تغيير مكالمة متكررة إلى ذيل عودية أو مكالمة تكرارية.

النظر في مشكلة حساب مضروب عدد.

النهج المباشر سيكون:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

لنفترض أنك اتصلت بالمضروب (4).شجرة العودية ستكون:

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1    

الحد الأقصى لعمق العودية في الحالة المذكورة أعلاه هو O(n).

ومع ذلك، خذ بعين الاعتبار المثال التالي:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

شجرة العودية لـ FactTail(4) ستكون:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

هنا أيضًا، الحد الأقصى لعمق العودية هو O(n) ولكن لا تضيف أي من الاستدعاءات أي متغير إضافي إلى المكدس.ومن ثم يمكن للمترجم التخلص من المكدس.

Answer 20

لفهم بعض الاختلافات الأساسية بين عودية الاستدعاء الخلفي وتكرارية الاستدعاء غير الخلفي، يمكننا استكشاف تطبيقات .NET لهذه التقنيات.

إليك مقالة تحتوي على بعض الأمثلة في C# وF# وC++\CLI: مغامرات في Tail Recursion في C# وF# وC++\CLI.

لا يتم تحسين C# لتكرار المكالمة الخلفية بينما يقوم F# بذلك.

تتضمن الاختلافات في المبدأ الحلقات مقابل الحلقات.حساب التفاضل والتكامل لامدا.تم تصميم C# مع وضع الحلقات في الاعتبار، بينما تم تصميم F# من مبادئ حساب التفاضل والتكامل Lambda.للحصول على كتاب جيد جدًا (ومجاني) عن مبادئ حساب التفاضل والتكامل لامدا، راجع هيكل وتفسير برامج الكمبيوتر، من قبل أبيلسون، سوسمان، وسوسمان.

فيما يتعلق بالمكالمات الخلفية في F#، للحصول على مقالة تمهيدية جيدة جدًا، راجع مقدمة تفصيلية للمكالمات الخلفية في F#.أخيرًا، إليك مقال يغطي الفرق بين التكرار غير الذيلي والتكرار الذيلي (في F#): الذيل العودية مقابل.العودية غير الذيلية في F حاد.

إذا كنت تريد أن تقرأ عن بعض الاختلافات في التصميم لتكرار الاستدعاء الخلفي بين C# وF#، فراجع إنشاء رمز تشغيل Tail-Call في C# وF#.

إذا كنت مهتمًا بدرجة كافية بمعرفة الشروط التي تمنع مترجم C# من إجراء تحسينات الاستدعاء الخلفي، فراجع هذه المقالة: شروط استدعاء الذيل JIT CLR.

Answer 21

هناك نوعان أساسيان من التكرارات: العودية الرأس و العودية الذيل.

في العودية الرأس, ، تقوم الوظيفة بإجراء مكالماتها المتكررة ثم تقوم ببعض الحسابات ، ربما باستخدام نتيجة المكالمة العودية ، على سبيل المثال.

في الذيل العودي الوظيفة ، تحدث جميع الحسابات أولاً والمكالمة العودية هي آخر شيء يحدث.

مأخوذ من هذا وظيفة فائقة رهيبة.يرجى النظر في قراءتها.

Answer 22

العودية تعني دالة تستدعي نفسها.على سبيل المثال:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Tail-Recursion يعني التكرار الذي ينهي الوظيفة:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

انظر، آخر شيء تفعله الدالة غير المنتهية (الإجراء، في مصطلحات المخطط) هو استدعاء نفسها.مثال آخر (أكثر فائدة) هو:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

في الإجراء المساعد، آخر شيء تفعله إذا لم يكن اليسار صفرًا هو استدعاء نفسه (بعد سلبيات شيء وcdr شيء).هذا هو في الأساس كيفية تعيين القائمة.

يتمتع التكرار الخلفي بميزة كبيرة تتمثل في أن المترجم (أو المترجم، الذي يعتمد على اللغة والبائع) يمكنه تحسينه، وتحويله إلى شيء يعادل حلقة while.في واقع الأمر، في تقليد المخطط، يتم إجراء معظم حلقات "for" و"while" بطريقة التكرار الخلفي (لا يوجد for و while، على حد علمي).

Answer 23

هذا السؤال يحمل الكثير من الإجابات الرائعة..لكن لا يسعني إلا أن أتناغم مع بديل حول كيفية تحديد "عودة الذيل" ، أو على الأقل "عودة الذيل المناسبة". يسمى:هل ينبغي للمرء أن ينظر إليها على أنها خاصية لتعبير معين في البرنامج؟أو ينبغي للمرء أن ينظر إليها على أنها خاصية ل تنفيذ لغة البرمجة?

لمعرفة المزيد عن وجهة النظر الأخيرة، هناك الكلاسيكية ورق بقلم ويل كلينجر، "التكرار الخلفي المناسب وكفاءة المساحة" (PLDI 1998)، الذي عرّف "التكرار الخلفي المناسب" كخاصية لتطبيق لغة البرمجة.تم إنشاء التعريف للسماح للمرء بتجاهل تفاصيل التنفيذ (مثل ما إذا كان مكدس الاستدعاءات يتم تمثيله فعليًا عبر مكدس وقت التشغيل أو عبر قائمة الإطارات المرتبطة المخصصة للكومة).

ولتحقيق ذلك، فإنه يستخدم التحليل المقارب:ليس من وقت تنفيذ البرنامج كما يرى المرء عادة، بل من البرنامج استخدام الفضاء.بهذه الطريقة، يصبح استخدام المساحة للقائمة المرتبطة المخصصة للكومة مقابل مكدس استدعاءات وقت التشغيل متكافئًا بشكل غير مقارب؛لذلك يجب على المرء أن يتجاهل تفاصيل تنفيذ لغة البرمجة (وهي تفاصيل مهمة بالتأكيد إلى حد ما في الممارسة العملية، ولكنها يمكن أن تعكر الأمور قليلاً عندما يحاول المرء تحديد ما إذا كان تنفيذ معين يلبي متطلبات أن يكون "ذيل الخاصية متكررًا" )

المقال يستحق الدراسة المتأنية لعدة أسباب:

• ويعطي تعريفا استقرائيا لل تعبيرات الذيل و مكالمات الذيل من البرنامج.(يبدو أن هذا التعريف، وسبب أهمية هذه المكالمات، هو موضوع معظم الإجابات الأخرى الواردة هنا.)

  فيما يلي هذه التعريفات، فقط لإضفاء نكهة على النص:

  التعريف 1 ال تعبيرات الذيل يتم تعريف البرنامج المكتوب في المخطط الأساسي بشكل استقرائي على النحو التالي.

  1. جسد تعبير لامدا هو تعبير ذيل
  2. لو (if E0 E1 E2) هو تعبير الذيل، ثم على حد سواء E1 و E2 هي تعبيرات الذيل.
  3. لا شيء آخر هو تعبير الذيل.

  التعريف 2 أ مكالمة الذيل هو تعبير ذيل وهو استدعاء إجراء.

(استدعاء ذيل متكرر، أو كما تقول الورقة، "استدعاء ذيل ذاتي" هو حالة خاصة من استدعاء ذيل حيث يتم استدعاء الإجراء نفسه.)

• يوفر تعريفات رسمية لستة "أجهزة" مختلفة لتقييم المخطط الأساسي، حيث يكون لكل جهاز نفس السلوك الملحوظ يستثني ل مقارب فئة التعقيد المكاني التي ينتمي إليها كل منهم.

  على سبيل المثال، بعد إعطاء تعريفات للآلات، على التوالي، 1.إدارة الذاكرة على أساس المكدس، 2.جمع القمامة ولكن لا يوجد مكالمات ذيل، 3.جمع البيانات المهملة والمكالمات الخلفية، تستمر الورقة في المضي قدمًا من خلال إستراتيجيات إدارة التخزين الأكثر تقدمًا، مثل 4."التكرار الذيل evlis"، حيث لا تحتاج البيئة إلى الحفاظ عليها عبر تقييم وسيطة التعبير الفرعي الأخيرة في استدعاء الذيل، 5.الحد من بيئة الإغلاق ل فقط المتغيرات الحرة لهذا الإغلاق، و 6.ما يسمى بدلالات "آمنة للفضاء" كما حددها ابيل وشاو.

• ومن أجل إثبات أن الآلات تنتمي فعليًا إلى ستة فئات مختلفة من التعقيد الفضائي، تقدم الورقة، لكل زوج من الآلات قيد المقارنة، أمثلة ملموسة لبرامج من شأنها أن تكشف عن تفجير الفضاء المقارب على جهاز واحد دون الآخر.

---

(بقراءة إجابتي الآن، لست متأكدًا مما إذا كنت قد تمكنت بالفعل من التقاط النقاط الحاسمة في السؤال ورق الكلنجر.ولكن، للأسف، لا أستطيع تخصيص المزيد من الوقت لتطوير هذه الإجابة في الوقت الحالي.)

Answer 24

الدالة العودية هي الدالة التي يدعو في حد ذاته

يسمح للمبرمجين بكتابة برامج فعالة باستخدام الحد الأدنى من التعليمات البرمجية.

الجانب السلبي هو أنهم يستطيعون ذلك تسبب حلقات لا نهاية لها وغيرها من النتائج غير المتوقعة إذا لم يكتب بشكل صحيح.

سأشرح كلاهما وظيفة العودية البسيطة وظيفة العودية الذيل

لكي يكتب أ دالة عودية بسيطة

1. النقطة الأولى التي يجب مراعاتها هي متى يجب أن تقرر الخروج من الحلقة التي هي الحلقة إذا
2. والثاني هو ما هي العملية التي يجب القيام بها إذا كنا وظيفتنا الخاصة

من المثال المعطى:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

من المثال أعلاه

if(n <=1)
     return 1;

هو العامل الحاسم عند الخروج من الحلقة

else 
     return n * fact(n-1);

هل يجب القيام بالمعالجة الفعلية؟

اسمحوا لي أن أقسم المهمة واحدة تلو الأخرى لسهولة الفهم.

دعونا نرى ما سيحدث داخليًا إذا ركضت fact(4)

1. استبدال ن=4

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If فشلت الحلقة لذلك تذهب إلى else حلقة حتى تعود 4 * fact(3)

2. في الذاكرة المكدسة، لدينا 4 * fact(3)

   استبدال ن = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If فشلت الحلقة لذلك تذهب إلى else حلقة

لذلك يعود 3 * fact(2)

تذكر أننا أطلقنا على ```4 * الحقيقة(3)``

الإخراج ل fact(3) = 3 * fact(2)

حتى الآن المكدس لديه 4 * fact(3) = 4 * 3 * fact(2)

3. في الذاكرة المكدسة، لدينا 4 * 3 * fact(2)

   استبدال ن = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If فشلت الحلقة لذلك تذهب إلى else حلقة

لذلك يعود 2 * fact(1)

تذكر أننا اتصلنا 4 * 3 * fact(2)

الإخراج ل fact(2) = 2 * fact(1)

حتى الآن المكدس لديه 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

3. في الذاكرة المكدسة، لدينا 4 * 3 * 2 * fact(1)

   استبدال ن = 1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If الحلقة صحيحة

لذلك يعود 1

تذكر أننا اتصلنا 4 * 3 * 2 * fact(1)

الإخراج ل fact(1) = 1

حتى الآن المكدس لديه 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

وأخيراً نتيجة الحقيقة(4) = 4 * 3 * 2 * 1 = 24

ال العودية الذيل سيكون

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

1. استبدال ن=4

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If فشلت الحلقة لذلك تذهب إلى else حلقة حتى تعود fact(3, 4)

2. في الذاكرة المكدسة، لدينا fact(3, 4)

   استبدال ن = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If فشلت الحلقة لذلك تذهب إلى else حلقة

لذلك يعود fact(2, 12)

2. في الذاكرة المكدسة، لدينا fact(2, 12)

   استبدال ن = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If فشلت الحلقة لذلك تذهب إلى else حلقة

لذلك يعود fact(1, 24)

3. في الذاكرة المكدسة، لدينا fact(1, 24)

   استبدال ن = 1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If الحلقة صحيحة

لذلك يعود running_total

الإخراج ل running_total = 24

وأخيراً نتيجة الحقيقة (4،1) = 24

Answer 25

لقد شرح العديد من الأشخاص بالفعل العودية هنا.أود أن أذكر بعض الأفكار حول بعض المزايا التي يوفرها التكرار من كتاب "التزامن في .NET، الأنماط الحديثة للبرمجة المتزامنة والمتوازية" للكاتب ريكاردو تيريل:

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

فيما يلي أيضًا بعض الملاحظات المثيرة للاهتمام من نفس الكتاب حول التكرار الخلفي:

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

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

Answer 26

أ الذيل العودي الدالة هي دالة عودية حيث آخر عملية يتم إجراؤها قبل العودة هي إجراء استدعاء دالة عودية.أي أنه يتم إرجاع القيمة المرجعة لاستدعاء الدالة العودية على الفور.على سبيل المثال، سيبدو الرمز الخاص بك كما يلي:

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

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

على سبيل المثال، هذه دالة عاملية عودية قياسية في بايثون:

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

وهذه نسخة متكررة من الدالة المضروب:

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(لاحظ أنه على الرغم من أن هذا كود Python، إلا أن مترجم CPython لا يقوم بتحسين الاتصال، لذا فإن ترتيب الكود الخاص بك على هذا النحو لا يمنح أي فائدة في وقت التشغيل.)

قد تضطر إلى جعل التعليمات البرمجية الخاصة بك غير قابلة للقراءة قليلاً للاستفادة من تحسين الاتصال الخلفي، كما هو موضح في المثال العاملي.(على سبيل المثال، أصبحت الحالة الأساسية الآن غير بديهية بعض الشيء، و accumulator يتم استخدام المعلمة بشكل فعال كنوع من المتغير العام.)

لكن فائدة تحسين الاستدعاء الخلفي هي أنه يمنع أخطاء تجاوز سعة المكدس.(سأشير إلى أنه يمكنك الحصول على هذه الميزة نفسها باستخدام خوارزمية تكرارية بدلاً من خوارزمية متكررة.)

تحدث تجاوزات المكدس عندما يتم دفع عدد كبير جدًا من كائنات الإطار إلى مكدس الاستدعاءات.يتم دفع كائن الإطار إلى مكدس الاستدعاءات عند استدعاء دالة، ويتم إخراجه من مكدس الاستدعاءات عندما تعود الدالة.تحتوي كائنات الإطار على معلومات مثل المتغيرات المحلية وسطر التعليمات البرمجية الذي سيتم الرجوع إليه عندما تعود الوظيفة.

إذا كانت الدالة العودية الخاصة بك تقوم بإجراء عدد كبير جدًا من الاستدعاءات العودية دون الرجوع، فقد تتجاوز مكدس الاستدعاءات الحد الأقصى لكائن الإطار الخاص بها.(يختلف العدد حسب المنصة؛في Python يكون هناك 1000 كائن إطار افتراضيًا.) يؤدي هذا إلى حدوث خطأ تجاوز المكدس خطأ.(مهلا، هذا هو المكان الذي يأتي منه اسم هذا الموقع!)

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

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

Answer 27

العودية الخلفية سريعة جدًا مقارنة بالعودية العادية.إنه سريع لأن مخرجات مكالمة الأسلاف لن تتم كتابتها في مكدس للحفاظ على المسار.ولكن في العودية العادية، يتم كتابة جميع مخرجات استدعاءات السلف في المكدس للحفاظ على المسار.