هل يمكن تحويل كل متصاعدة إلى التكرار؟

Question

أ Reddit الموضوع طرح سؤال مثير للاهتمام على ما يبدو:

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

مثال (عداد؟) في المنشور هو الزوج:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Answer 1

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

في العديد من الحالات، تحويل وظيفة متكررة أمر سهل. تقدم Knuth عدة تقنيات في "فن برمجة الكمبيوتر". وفي كثير من الأحيان، يمكن حساب شيء محسوب بشكل متكرر من خلال نهج مختلف تماما في وقت أقل ومساحة. المثال الكلاسيكي لهذا هو أرقام فيبوناتشي أو تسلسلها. لقد قابلت هذه المشكلة بالتأكيد في خطة الدرجات الخاصة بك.

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

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

أستطيع أن أرى سبب مقنع واحد. لنفترض أنك نظام نموذجي في لغة مستوى عالي المستوى مثل [ارتدي الملابس الداخلية الأسبستوس] مخطط، LISP، Haskell، Ocaml، بيرل، أو باسكال. لنفترض أن الشروط تجعلك تحتاج إلى تنفيذ في ج أو جافا. (ربما تكون السياسة.)، وبالتالي يمكنك بالتأكيد بعض الوظائف المكتوبة بشكل متكرر ولكن، والتي، مترجم حرفيا، ستنفجر نظام التشغيل الخاص بك. على سبيل المثال، تعد عودة الذيل اللانهائي ممكن في مخطط، لكن المصطلح نفسه يسبب مشكلة في بيئات C الموجودة. مثال آخر هو استخدام وظائف متداخلة متعمدة والنطاق الثابت، الذي يدعم باسكال ولكن ج لا.

في هذه الظروف، قد تحاول التغلب على المقاومة السياسية للغة الأصلية. قد تجد نفسك reimplidenting LISP بشكل سيء، كما هو الحال في القانون العاشر من جرينسبون (اللسان داخل الخد). أو قد تجد مجرد نهج مختلف تماما للحل. ولكن في أي حال، هناك بالتأكيد طريقة.

Answer 2

هل من الممكن دائما كتابة نموذج غير متكرر لكل وظيفة متكررة؟

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

لسوء الحظ، أنا غير قادر على العثور على تعريف جيد، رسمي للغوتو عبر الإنترنت حتى هنا واحد:

برنامج Goto هو سلسلة من الأوامر ب أعدم على أ سجل الجهاز مثل ذلك ب هو واحد مما يلي:

• HALT, ، والتي توقف التنفيذ
• رديئة = رديئة + 1 أين رديئة هو أي سجل
• رديئة = رديئة – 1 أين رديئة هو أي سجل
• GOTO عاشر أين عاشر هو التسمية
• IF رديئة ≠ 0 GOTO عاشر أين رديئة هو أي سجل و عاشر هو التسمية
• تسمية، تليها أي من الأوامر أعلاه.

ومع ذلك، فإن التحويلات بين الوظائف المتكررة وغير العودية ليست دائما تافهة (إلا من خلال إعادة التنفيذ اليدوي الطائشي لمكدس المكالمات).

لمزيد من المعلومات هذه الإجابة.

Answer 3

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

Answer 4

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

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

Answer 5

• يمكن تمثيل تدفق تنفيذ الوظيفة العودية كشجرة.

• يمكن القيام بنفس المنطق بواسطة حلقة، والتي تستخدم بنية بيانات لاجتياز هذه الشجرة.

• يمكن إجراء اجتياز العمق الأول باستخدام مكدس، يمكن إجراء اجتيازات أول عرض باستخدام قائمة انتظار.

لذلك فإن الجواب هو نعم. لماذا: https://stackoverflow.com/a/531721/2128327..

هل يمكن لأي قوائم في حلقة واحدة؟ نعم لأن

آلة Turing يقوم بكل ما يفعله عن طريق تنفيذ حلقة واحدة:

1. جلب التعليمات،
2. تقييمها،
3. goto 1.

Answer 6

نعم، من الممكن دائما كتابة نسخة غير متكررة. الحل التافهة هو استخدام هيكل بيانات المكدس ومحاكاة التنفيذ التراكبي.

Answer 7

نعم، باستخدام كومة صراحة (لكن العودية أكثر متعة للقراءة، IMHO).

Answer 8

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

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

Answer 9

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

هذا أقل من مشكلة الآن، حيث تحولت الأزياء نحو التقنيات الأخرى.

Answer 10

يمكن حساب جميع الوظائف المحاسبة بواسطة آلات Turing وبالتالي أنظمة الأنظمة المتنقلة وآلات Turing (أنظمة تكرارية) تعادل.

Answer 11

إزالة العودية مشكلة معقدة وهي ممكنة في ظل ظروف محددة جيدا.

الحالات أدناه هي من بين السهل:

• recursion الذيل
• Recursion الخطي المباشر

Answer 12

Appart من المكدس الصريح، نمط آخر لتحويل العودية في التكرار هو استخدام الترامبولين.

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

يعمل هذا النهج لوظائف متكررة بشكل متبادل، لكنني أخشى أنه يعمل فقط من أجل مكالمات الذيل.

http://en.wikipedia.org/wiki/trampoline_(Computers)

Answer 13

أود أن أقول نعم - دعوة الوظيفة ليست سوى انتقلت وعملية مكدس (تقريبا). كل ما عليك فعله هو تقليد المكدس الذي تم بناؤه أثناء استدعاء الوظائف والقيام بشيء مشابه مثل Goto (يمكنك تقليد Gotos باللغات التي لا تملك هذه الكلمة الرئيسية بشكل صريح أيضا).

Answer 14

إلقاء نظرة على الإدخالات التالية على Wikipedia، يمكنك استخدامها كنقطة انطلاق للعثور على إجابة كاملة على سؤالك.

• العودية في علوم الكمبيوتر
• علاقة تكرارية

يتبع الفقرة التي قد تعطيك بعض التلميحات على من أين تبدأ:

حل علاقة تكرار تعني الحصول على حل مغلق: وظيفة غير متكررة من n.

إلقاء نظرة أيضا على الفقرة الأخيرة من هذا الإدخال.

Answer 15

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

المزيد من التفاصيل: https:/developer.mozilla.org/en-us/docs/web/javascript/guide/functions.

Answer 16

Tazzego، العودية تعني أن وظيفة ستدعو نفسه سواء كنت ترغب في ذلك أم لا. عندما يتحدث الناس حول ما إذا كان يمكن القيام بأشياء دون إصدارات أم لا، فإنها تعني ذلك ولا يمكنك القول "لا، وهذا ليس صحيحا، لأنني لا أتفق مع تعريف العودية" كبيان صالح.

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

بالمناسبة، هناك لغات كاملة تورينج لا تنفذ فقط العودية (مثل SML) كوسيلة للحلقات. توجد أيضا لغات كاملة تورينج لتطبيق التكرار فقط كوسيلة للحلقات (مثل FORTRAN IV). تثبت أطروحة تورينج الكنيسة أنه يمكن القيام بأي شيء ممكن في اللغات الزمنية فقط في لغة غير متكررة وفيسسا - العكس من حقيقة أن كلاهما لديهما ملكية تورينج.

Answer 17

هنا خوارزمية تكرارية:

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end