Quyruq recursiyası nədir?

Mən lisp öyrənməyə başlamış olsam da, quyruq-recursiv termini rastladım. Bu nə deməkdir?

1429
29 авг. Ben Lever tərəfindən təyin olunan Aug 29 2008-08-29 06:48 '08 at 6:48 2008-08-29 06:48
@ 24 cavab

İlk N tamsayıları əlavə edən sadə bir funksiyanı nəzərdən keçirin. (məsələn, sum(5) = 1 + 2 + 3 + 4 + 5 = 15 ).

Burada recursion istifadə edən sadə bir JavaScript proqramı:

 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 

Qeyd edək ki, hər bir təkrarlanan zəng, JavaScript tercümanı həqiqətən, məbləği hesablamağa başlamazdan əvvəl edilməlidir.

Eyni funksiyanın quyruq-recursiv versiyası:

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

Tullantıların running_total hər recursive çağırış qiymətləndirmə ilə yenilənir.

Qeyd Orijinal cavab Pythondan misallardan istifadə etmişdir. Onlar JavaScript-yə dəyişdirildi, çünki müasir JavaScript- lərin tailing optimizasiyası dəstəklənir, lakin Python tərcüməçiləri yoxdur.

1417
31 авг. Cavab Lorin Hochstein 31 avqustda verilir. 2008-08-31 21:21 '08 saat 09:21 'da 2008-08-31 21:21

Ənənəvi recursionda tipik bir model ilk növbədə təkrarlanan zənglərinizi yerinə yetirir və sonra təkrarlanan zəngin qaytarılması dəyərini götürün və nəticəni hesablayın. Beləliklə, hər recursive zəngdən sonra qayıdana qədər hesablamalarınızın nəticəsini əldə etməyəcəksiniz.

Quyruq recursionunda əvvəlcə hesablamaları yerinə yetirirsiniz və sonra cari addımın nəticələrini növbəti recursive addımda keçərək, təkrarlanan bir zəng aparırsınız. Bu sonuncu bəyanatın forma olduğunu göstərir (return (recursive-function params)) . Əslində, hər hansı bir təkrarlanan addımın qaytarma dəyəri növbəti recursiv çağırışın qaytarılması dəyəri ilə eynidır .

border=0

Bunun sonucu, növbəti recursive addımı yerinə yetirməyə hazır olduğunuzda artıq mövcud yığın çərçivəsinə ehtiyacınız yoxdur. Bu, bəzi optimallaşdırmaya imkan verir. Əslində, düzgün bir yazılı kompilyatorla, quyruq təkrarlanan çağırışla heç vaxt bir araçıya sahib olmamalısınız. Sadəcə, növbəti recursive addım üçün mövcud yığın çərçivəsini istifadə edin. Lisp bunu edir.

598
29 авг. cavab 29 avqustda user316 tərəfindən verilir . 2008-08-29 06:57 '08 at 6:57 2008-08-29 06:57

Əhəmiyyətli olan nöqtə kuyruğunun təkrarlanması, əslində bir döngəyə bərabərdir. Bu, yalnız kompüter optimallaşdırılması məsələsidir, həm də ifadəli olmağın əsas faktorudır. Bu hər iki istiqamətdə də baş verir: hər hansı forma dövrü keçə bilərsiniz

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

Əlbəttə, bəzi dəyişənlər üçün bəzi maraqlı dəyərləri hesablamaq üçün E , SQ müəyyən edilməlidir. Məsələn, velosiped funksiyası

 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); } 

(Kuyruğun təkraredici funksiyasının bu "sarmalçı" daha az parametrli bir funksiya ilə ümumi funksional idiomdur.)

177
31 авг. Chris Conway tərəfindən verilmiş cavab 31 avqust 2008-08-31 20:29 '08 saat 20:29 'da 2008-08-31 20:29

"Lua'da Proqramlaşdırma" kitabından alınan bu alınış düzgün quyruq təkrarlanmasının necə olduğunu göstərir (Lua'da, həm də Lisp üçün tətbiq olunmalıdır) və niyə daha yaxşıdır.

Zəngin quyruğu [quyruq recursion] zəng kimi gizli bir növdür. Bir quyruq çağırışı funksiya sonuncu hərəkət kimi başqa bir çağırdıqda baş verir, buna görə daha çox bir şey yoxdur. Məsələn, aşağıdakı g çağırışı quyruq zəngidir:

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

... Daha əvvəl söylədiyim kimi, quyruq zəngləri goto görünüşüdür. Belə ki, Lua-da düzgün quyruğu zənglərin çox faydalı tətbiqi dövlət maşınlarının proqramlaşdırılması üçün nəzərdə tutulmuşdur. Belə ərizələr hər bir dövlətin funksiyası ilə təmsil edə bilər; dəyişdirmə vəziyyəti müəyyən bir funksiyaya keçmək (və ya çağırmaq) deməkdir. Məsələn, sadə labirent oyununa nəzər salaq. Labirintdə dörd qapısı olan bir neçə otaq var: şimal, cənub, şərq və qərb. Hər bir addımda istifadəçi hərəkət istiqaməti daxil olur. Bu istiqamətdə bir qapı varsa, istifadəçi müvafiq otaqda gedər; əks halda proqram bir xəbərdarlıq göstərir. Məqsəd, başlanğıc otağından son nömrəyə keçməkdir.

Bu oyun cari otaq bir dövlət olduğu tipik dövlət maşınıdır. Hər bir otaq üçün bir funksiya ilə belə bir labirent həyata keçirə bilərik. Bir otaqdan digərinə keçmək üçün quyruq zənglərindən istifadə edirik. Dörd otaqlı kiçik bir labirent bu kimi görünə bilər:

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

Bu recursion deyil, çünki təkrarlanan çağırışdan sonra bu funksiyanı yerinə yetirmək üçün lazım olan hər şeyi (əlavə edin 1). Çox sayda girdiyseniz, bu ehtimal yığını daşmasına səbəb olacaq.

124
29 авг. Cavab Hoffman 29 avqustda verilir . 2008-08-29 19:03 '08 saat 19:03 'da 2008-08-29 19:03

Normal recursion istifadə edərək, hər recursive zəng zəng yığınında fərqli bir giriş qoyur. Təkrarlanma tamamlandıqda, ərizə hər bir qeydin tamamilə geri çəkilməlidir.

Kuyruktaki recursion istifadə edərkən, dilə bağlı olaraq, derleyici yığını bir qeydə qatlaya bilər, beləliklə yığını boş saxlaya bilərsiniz ... Böyük bir təkrarlanan sorgu, həqiqətən, yığın daşmasına səbəb ola bilər.

Əsasən quyruq təkrarlanmaları təkrarlama ilə optimallaşdırıla bilər.

62
29 авг. Cavab FlySwat 29 avqustda verilir . 2008-08-29 06:55 '08 saat 06:55 'da 2008-08-29 06:55

Bunu sözlərlə izah etmək əvəzinə burada bir nümunədir. Bu faktöryel funksiyalı diaqramdır:

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

Birinci versiyada, bir həqiqətə bir təkrarlanan çağırışın çarpma ifadəinə bəsləndiyini və buna görə təkrarlanan çağırış edildikdə dövlət yığında saxlanılmalıdır. Tail-recursive versiyada recursiv çağırışın dəyərini gözləyən başqa bir S-ifadəsi yoxdur və heç bir addımın tələb olunmasından sonra dövlətin yığında saxlanmasına ehtiyac yoxdur. Bir qayda olaraq, quyruq recursiv dövr funksiyaları daimi yığım məkanından istifadə edir.

61
29 авг. Avqustun 29-da Kyle Cronin tərəfindən verilmiş cavab 2008-08-29 06:57 '08 at 6:57 2008-08-29 06:57

Yargon faylı quyruq recursion tərifi haqqında danışır:

quyruğu recursion /n./

Əgər bundan artıq yorulmuyorsanız, quyruğunun təkrarlanmasına baxın.

60
29 авг. Cavab 29 yanvarda verilir . 2008-08-29 10:21 '08 saat 10:21 'da 2008-08-29 10:21

Kuyruk recursion, özyinelemeli çağrının özyinelemeli algoritmada sonuncu mantıklı talimatta sonuncağı olduğunu bildirir.

Yəqin ki, recursion-da, recursive zəngləri dayandırır və zəng yığını yaratmaq başlayır bir əsas qeydiyyatdan var. Klassik nümunədən istifadə etmək üçün Lispdən daha çox C-iş olsa da, faktöryor funksiya quyruq təkrarlanmasını göstərir. Əsas vəziyyətin yoxlanılmasından sonra təkrarlanan çağrı baş verir.

28
29 авг. Peter Meyer tərəfindən verilmiş cavabı 29 Avqust. 2008-08-29 06:57 '08 at 6:57 2008-08-29 06:57

Demək ki, təlimat göstəricisi yığını üzərinə basmaq yerinə, təkrarlanan funksiyanın üst hissəsinə keçə və icraya davam edə bilərsiniz. Bu, olmadan sonsuz recursion funksiyaları yerinə yetirmək üçün imkan verir.

Yığın çərçivələrinin necə göründüyünə dair qrafik nümunələr olduğu mövzuda bir blog yazısı yazdım.

25
01 сент. 01 Sentyabrda Chris Smith tərəfindən verilmiş cavab 2008-09-01 02:52 '08 saat 02:52 'da 2008-09-01 02:52

Burada iki funksiyanı müqayisə edən sürətli kod parçasıdır. Birincisi, müəyyən bir sayı faktöryelini tapmaq üçün ənənəvi recursiondur. İkinci quyruq recursion istifadə edir.

Çox sadə və intuitiv.

Bir özyinelemeli funksiyanı əsas vəziyyətdə müəyyən bir dəyər qaytarırsa quyruq təkrar edirmi müəyyən etmək üçün sadə bir yol. Bu, 1 və ya həqiqətə və ya bir şeyə dönməyidir. Çox güman ki, metod parametrlərindən birinin bəzi versiyasını qaytaracaq.

Təkrarlanan çağırış hər hansı əlavədən, hesab əməliyyatlarından, dəyişikliklərdən və s. Bu təkrarlanan çağırış deməkdir.

17
19 дек. Cavab 19 dekabrda Əbu Zübeyr tərəfindən verilir . 2010-12-19 18:52 '10 at 06:52 PM 2010-12-19 18:52

tail call recursion anlamaq üçün ən yaxşı yoldur, son çağırış (və ya quyruq zəng) funksiyasının özü olduğu xüsusi recursion haldır.

Python'da təqdim olunan nümunələri müqayisə etmək:

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

^ RECURSION

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

^ TAIL RECURSION

Ümumi recursive versiyasını görə x + recsum(x - 1) kimi, kod blokundakı son zəng x + recsum(x - 1) . Beləliklə, recsum üsulu recsum sonra x +.. başqa bir əməliyyat var x +..

Bununla yanaşı, quyruq təkrarlanan versiyada, kod blokundakı son çağırış (və ya quyruq zəng) tailrecsum(x - 1, running_total + x) yəni sonuncu çağırış metodun özü üçün nəzərdə tutulur və bundan sonra heç bir əməliyyat aparılmır.

Bu an əhəmiyyətlidir, çünki burada görüldüyü kimi, quyruq təkrarlanması yaddaşını artırmaz, çünki əsas virtual maşın özünü quyruq mövqeyində zənginləşdirən funksiyanı gördükdə (funksiyada qiymətləndirilməlidir ki, sonuncu ifadə), mövcud çərçivəni yığın, Tail Call Optimization (TCO) kimi tanınır.

EDIT

Nb. Unutmayın ki, yuxarıda göstərilən nümunə Python-da yazılıdır, onların iş müddəti TCO-nu dəstəkləmir. Bu nöqtəni izah etmək üçün yalnız bir nümunədir. TCO, Scheme, Haskell və s. Kimi dillərdə dəstəklənir.

13
21 дек. Abhiroop Sarkar tərəfindən verilmiş cavab 21 dekabr 2015-12-21 14:47 '15 'də 2:47 pm' de 2015-12-21 14:47

Java'da, burada Fibonacci funksiyasının quyruq təkrarlanan tətbiqini tapa bilərsiniz:

 public int recursive(final int n) { if (n <= 2) return 1; return recursive(n - 1) + recursive(n - 2); } 
11
15 окт. 15 oktyabrda jorgetown tərəfindən verilmiş cavab . 2008-10-15 00:20 '08 at 0:20 2008-10-15 00:20

Aşağıda, quyruq recursionunu istifadə edərək faktiki istifadə edən ümumi Lisp nümunəsidir. Bir yığın olmaması səbəbiylə insanely böyük faktöryel hesablamalar aparmaq mümkün idi ...

10
11 марта '12 в 9:07 2012-03-11 09:07 Cavab 11 mart 2012-ci il tarixində saat 9 : 07 -da 09 : 09 -da user922475 tərəfindən verilmişdir

Qısacası, quyruq recursionunda bir funksiyada sonuncu bəyanat kimi təkrarlanan çağırış var, buna görə təkrarlanan çağırışı gözləmək lazım deyil.

Belə ki, bu, quyruğu təkrar edir, yəni. N (x - 1, p * x) funksiyasında ən son operatordur, burada kompilyator akıllıdır, bunun dövrü (faktöryel) üçün optimallaşdırıla biləcəyini anlamaq üçün. İkinci parametr p, məhsulun ara dəyərini daşıyır.

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

Yuxarıda göstərilən faktöryə funksiyanı yazmağın qeyri-recursiv üsuludur (baxmayaraq ki, bəzi C ++ tərtibatçıları bunu hər halda optimallaşdıra bilərlər).

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

lakin bu deyil:

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

Mən uzun bir yazı yazdım " Tail Recursion Overview - Visual Studio C + + - Məclis görünüşü "

2019

09 нояб. Cavab ədalətlidir 09 noyabr. 2016-11-09 02:21 '16 at 2:21 AM 2016-11-09 02:21

Mən bir Lisp proqramçı deyiləm, amma kömək olacağını düşünürəm.

Əsasən bu bir proqramlaşdırma tərzidir, buna görə təkrarlanan zəng etdiyiniz son şeydir.

8
29 авг. Cavab Matt Hamilton tərəfindən verilmiş Aug 29 2008-08-29 06:50 '08 saat 06:50 'da 2008-08-29 06:50

Burada yuxarıda qeyd olunan tailrecsum funksiyasının perl versiyası tailrecsum .

8
02 окт. Cavab Brad Gilbert 02 oktyabr tərəfindən verildi . 2008-10-02 01:06 '08 at 01:06 2008-10-02 01:06

Bu quyruq təkrarlanan kompüter proqramlarının strukturundan və şərhindən alınmış bir nəticədir.

Yineleme ve özyinelemeden farklı olaraq, yinelemeli bir prosedür kavramıyla özyinelemeli bir süreç kavramını çelişmemeye dikkat etmeliyiz. Yuxarıdakı bir proseduru təsvir etdikdə, prosedurun tərifinin prosedurun özünə (doğrudan və ya dolayı yolla) aid olduğunu göstərən sintaktik bir faktdır. Ancaq bir prosesi aşağıdakı kimi izah edəndə, linearly recursive, biz bu prosesin necə inkişafından danışırıq və prosedur yazma sintaksisindən danışmırıq. Faktorinq kimi təkraredici bir prosedura istinadən, yineleyici bir proses yaratdığımız üçün narahat olur. Ancaq proses həqiqətən yineleyicidir: dövlət üç dövlət dəyişkənliyi ilə tam şəkildə müəyyən edilir və tərcüməçinin prosesi icra etmək üçün yalnız üç dəyişənləri izləmək lazımdır.

Proses və prosedur arasındakı fərqlərin baş verə biləcəyi səbəblərindən biri də ümumi dillərin (Ada, Paskal və C daxil olmaqla) ən çox tətbiqi, hər hansı bir recursive prosedurun şərhinin, prosedur çağırışlarının sayı, təsvir edilən prosedura əsasən yinelərsə belə. Bunun nəticəsi olaraq, bu dillər təkrarlanan prosesləri, yalnız, təkrarlamaq, əvvəlcədən, və ya olduğu kimi, xüsusi "çevik konstruksiyalara" müraciət edərək təsvir edə bilər. Sxemin tətbiqi bu çatışmazlığı paylaşmır. Yenidən təkrarlanan prosedur ilə təkrarlanan proses olsa da, sabit məkanda təkrarlanan prosesi həyata keçirəcəkdir. Bu əmlakla bir tətbiq quyruq recursion adlanır. Tail-recursive həyata keçirmə, yineleme adi proseduru çağırma mexanizmi istifadə edilə bilər, belə ki, xüsusi iterativ konstruksiyalar sintaktik şəkər kimi faydalıdır.

7
27 июня '16 в 12:41 2016-06-27 12:41 cavab ayushgp tərəfindən verilir 27 iyun 'da saat 12:41' də 2016-06-27 12:41

Kuyruksuz təkrarlanma hazırda yaşadığınız həyatdır. Siz "əvvəlki" çərçivəyə qayıtmaq üçün heç bir səbəb və ya vasitələr olmadığı üçün həmişə eyni yığın yığını təkrar təkrar yığırsınız. Keçmiş və keçmişdir, buna görə atılmaq mümkündür. Prosesiniz qaçılmaz olaraq ölməyincə, əbədi olaraq gələcəkdə hərəkət edən bir çərçivə əldə edirsiniz.

Bəzi proseslər əlavə çərçivələrdən istifadə edə biləcəyini düşünürsənsə, analoq pozulur, ancaq yığın müəyyən müddətdə yetişməsə də, quyruq təkrarlayıcı hesab olunur.

6
23 дек. Cavab user633183 23 dekabr tərəfindən verilir . 2016-12-23 21:04 '16 at 21:04 2016-12-23 21:04

Tail Call recursion və qeyri-zəng axtarış nüsxəsi arasında əsas fərqlərin bir hissəsini anlamaq üçün, bu texnologiyaların .NET-də tətbiqini araşdıra bilərik.

C #, F # və C ++ \ CLI-də bəzi nümunələri olan bir məqalə: C #, F # və C ++ \ CLI də quyruğu təkrarlanmasında sərgüzəştlər .

C # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # *

Əsas fərqlər lambda hesabına qarşı dövrü əhatə edir. C # lambda hesabında inşa edildikdə, nəzərə alındıqca dövrlər nəzərdə tutulur. Lambda calculus prinsipləri haqqında çox yaxşı (və pulsuz) kitab üçün, Abelson, Sussman və Sussman tərəfindən "Kompüter proqramlarının strukturu və təfsiri " adlı bölməsinə baxın.

F #-də quyruq zənglərinə gəldikdə, çox yaxşı bir giriş məqaləsi üçün, F #-də quyruq zənglərinə ətraflı giriş baxın. Nəhayət, quyruq zəngindən (F #) istifadə edərək, recursion olmadan recursion ilə fərqi müzakirə edən bir məqalə var: F kəskin bir kuyruksuz quyruğu ilə recursion .

C # və F # arasında quyruq çağrısı recursionu arasında bəzi dizayn fərqlərindən bəhs etmək istəyirsinizsə, C # və F # ilə Tail-Call opcode yaradın .

C # tərtibçisinin quyruq çağırışını optimallaşdırmaq üçün hansı şəraitin qarşısını almadığını bilmək üçün bu yazıya baxın: JIT CLR quyruq zəngləri şərtləri .

5
28 апр. Cavab devinbost Apr 28 2014-04-28 22:13 '14 at 10:13 PM 2014-04-28 22:13

Quyruq recursionu bir funksiyadan sonrakı ("quyruq") çağırır ki, bir recursive funksiyasıdır. Bir çox tərtibçi bir recursive və ya yineleyici zəngə bir recursive zəng dəyişdirmək optimize.

Bir sıra faktöryel hesablama problemini düşünün.

Birbaşa yanaşma olardı:

  factorial(n): if n==0 then 1 else n*factorial(n-1) 

Faktiki olaraq zəng edin (4). Nümunə ağacı aşağıdakı olardı:

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

Yuxarıdakı vəziyyətdə maksimal recursion dərinliyi O (n) dir.

Lakin, aşağıdakı nümunəni nəzərdən keçirin:

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

FactTail (4) üçün recursion ağacı aşağıdakılardır:

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

Burada da maksimum recursion dərinliyi O (n), lakin zənglərdən heç biri əlavə yığışmaya ek əlavə dəyişiklik əlavə etmir. Buna görə kompilyator yığını çıxara bilər.

5
23 дек. cavab coding_ninza 23 dekabr. 2017-12-23 15:26 '17 saat 15:26 'də 2017-12-23 15:26' də

Təkrarlanma özünü zəng edən funksiyanı nəzərdə tutur. Məsələn:

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

Видите, последнее, что делает незавершенная функция (процедура, на языке жаргона Scheme), - это вызывает себя. Другой (более полезный) пример:

4
ответ дан magice 02 сент. '08 в 17:08 2008-09-02 17:08

Существует два основных вида рекурсии: рекурсия головы и рекурсия хвоста.

В рекурсии головы функция выполняет свой рекурсивный вызов, а затем выполняет еще несколько вычислений, например, используя результат рекурсивного вызова.

В хвостовой рекурсивной функции все вычисления выполняются первыми, а рекурсивный вызов - последним.

Взято из этого супер классного поста. Пожалуйста, подумайте над прочтением.

4
ответ дан Abdullah Khan 08 мая '18 в 13:09 2018-05-08 13:09

В этом вопросе есть много отличных @... но я не могу не ответить на альтернативный подход, как определить "рекурсию хвоста" или, по крайней мере, "правильную рекурсию хвоста". А именно: следует ли рассматривать его как свойство определенного выражения в программе? Или следует рассматривать его как свойство реализации языка программирования?

Более подробно о последнем представлении есть классический paper Will Clinger, "Надлежащая рекурсия хвоста и эффективность пространства" (PLDI 1998), которая определила "правильную рекурсию хвоста" как свойство реализации языка программирования. Определение сконструировано так, чтобы можно было игнорировать детали реализации (например, действительно ли стек вызовов фактически представлен через стек времени выполнения или через связанный с кучей связанный список кадров).

Чтобы достичь этого, он использует асимптотический анализ: не время выполнения программы, как обычно видит, а скорее использование программного пространства. Таким образом, использование пространства связанного с кучей списка ссылок и стека вызовов времени выполнения оказывается асимптотически эквивалентным; поэтому можно игнорировать эту деталь реализации реализации языка программирования (деталь, которая, безусловно, имеет значение практически на практике, но может немного загрязнять воды, когда вы пытаетесь определить, удовлетворяет ли данная реализация требованию "рекурсивный хвост свойства" ) )

Статья заслуживает тщательного изучения по ряду причин:

  • Он дает индуктивное определение хвостовых выражений и хвостовых вызовов программы. (Такое определение и почему такие призывы важны, кажется, являются предметом большинства других @, приведенных здесь.)

    Вот эти определения, просто чтобы обеспечить вкус текста:

    Определение 1 . Выражения хвоста программы, записанные в Core Scheme, определяются индуктивно следующим образом.

    • Тело выражения лямбда - это выражение хвоста
    • Если (if E0 E1 E2) является хвостовым выражением, то и E1 , и E2 являются хвостовыми выражениями.
    • Ничто другое не является выражением хвоста.

    Определение 2 Хвост-вызов - это выражение хвоста, которое является вызовом процедуры.

(хвостовой рекурсивный вызов, или, как говорится в документе, "вызов с собственным хвостом" является частным случаем хвостового вызова, в котором сама процедура вызывается).

  • Он предоставляет формальные определения для шести разных "машин" для оценки Core Scheme, где каждая машина имеет одно и то же наблюдаемое поведение, за исключением класса асимптотической сложности пространства, в котором находится каждый.

    Например, после определения определений для машин, соответственно, 1. управление памятью на основе стека, 2. сбор мусора, но отсутствие хвостовых вызовов, 3. сбор мусора и хвостовые звонки, бумага продолжается вперед с еще более продвинутыми стратегиями управления хранением, например 4. "evlis tail recursion", где окружающая среда не нуждается в сохранении во время оценки последнего аргумента подвыражения в хвостовом вызове, 5. сокращение среды замыкания только до бесплатных переменных этого закрытие и 6. так называемая "безопасная для космоса" семантика, как определено Аппель и Шао .

  • Чтобы доказать, что машины фактически принадлежат шести различным классам сложности пространства, бумага для каждой пары сравниваемых машин предоставляет конкретные примеры программ, которые будут вызывать разложение асимптотического пространства на одной машине, но не другие.


(Прочитав мой ответ сейчас, я не уверен, что мне удалось фактически захватить критические точки " Клиринговая бумага" . Но, увы, я не могу посвятить больше времени на разработку этого ответа прямо сейчас.)

3
ответ дан pnkfelix 05 июля '17 в 13:51 2017-07-05 13:51

Многие люди уже объяснили рекурсию здесь. Я хотел бы привести пару соображений о некоторых преимуществах, которые дает рекурсия из книги Риккардо Террелла "Параллелизм в .NET, Современные шаблоны параллельного и параллельного программирования":

"Функциональная рекурсия - это естественный способ итерации в FP, поскольку она позволяет избежать изменения состояния. Во время каждой итерации в конструктор цикла передается новое значение, а не обновляется (мутирует). Кроме того, рекурсивная функция может быть составлена, делая Ваша программа более модульная, а также предоставляет возможности для использования распараллеливания. "

Вот также некоторые интересные заметки из той же книги о хвостовой рекурсии:

Хвостовая рекурсия - это метод, который преобразует обычную рекурсивную функцию в оптимизированную версию, которая может обрабатывать большие входные данные без каких-либо рисков и побочных эффектов.

П р и м е ч а н и е - Основная причина использования хвостового вызова в качестве оптимизации заключается в улучшении локальности данных, использования памяти и использования кэша. Выполняя оконечный вызов, вызываемый абонент использует то же пространство стека, что и вызывающий. Это уменьшает нагрузку на память. Это незначительно улучшает кэш, потому что та же самая память повторно используется для последующих вызывающих абонентов и может оставаться в кеше, вместо того, чтобы выселять более старую строку кеша, чтобы освободить место для новой строки кеша.

1
ответ дан Vadim S. 04 янв. '19 в 12:19 2019-01-04 12:19

Другие вопросы по меткам > или Задайте вопрос