Hännän rekursio määritellään rekursiiviseksi funktioksi, jossa rekursiivinen kutsu on viimeinen funktion suorittama lause. Joten periaatteessa mitään ei jää suoritettavaksi rekursiokutsun jälkeen.
Esimerkiksi seuraava C++-funktio print() on tail rekursiivinen.
C
// An example of tail recursive function> void> print(>int> n)> {> >if> (n <0)> >return>;> >printf>(>'%d '>, n);> >// The last executed statement is recursive call> >print(n - 1);> }> |
>
>
C++
// An example of tail recursive function> static> void> print(>int> n)> {> >if> (n <0)> >return>;> >cout <<>' '> << n;> > >// The last executed statement is recursive call> >print(n - 1);> }> // This code is contributed by Aman Kumar> |
>
>
Java
// An example of tail recursive function> static> void> print(>int> n)> {> >if> (n <>0>)> >return>;> >System.out.print(>' '> + n);> >// The last executed statement> >// is recursive call> >print(n ->1>);> }> // This code is contributed by divyeh072019> |
>
>
Python 3
# An example of tail recursive function> def> prints(n):> >if> (n <>0>):> >return> >print>(>str>(n), end>=>' '>)> ># The last executed statement is recursive call> >prints(n>->1>)> ># This code is contributed by Pratham76> ># improved by ashish2021> |
>
>
C#
// An example of tail recursive function> static> void> print(>int> n)> {> >if> (n <0)> >return>;> >Console.Write(>' '> + n);> >// The last executed statement> >// is recursive call> >print(n - 1);> }> // This code is contributed by divyeshrabadiya07> |
>
>
Javascript
> // An example of tail recursive function> function> print(n)> {> >if> (n <0)> >return>;> > >document.write(>' '> + n);> > >// The last executed statement> >// is recursive call> >print(n - 1);> }> // This code is contributed by Rajput-Ji> > |
>
>
Aika monimutkaisuus: Päällä)
Aputila: Päällä)
Tarve häntärekursiolle:
Tail-rekursiivisia funktioita pidetään parempana kuin ei-häntärekursiivisia toimintoja, koska kääntäjä voi optimoida häntärekursiota.
Kääntäjät suorittavat yleensä rekursiiviset proseduurit käyttämällä a pino . Tämä pino sisältää kaikki asiaankuuluvat tiedot, mukaan lukien parametriarvot, jokaiselle rekursiiviselle kutsulle. Kun menettelyä kutsutaan, sen tiedot ovat työnnettiin pinoon, ja kun toiminto päättyy, tieto on poksahti pois pinosta. Siten ei-tail-rekursiivisille funktioille pinon syvyys (enimmäismäärä käytetty pinotilaa milloin tahansa kääntämisen aikana) on enemmän.
Kääntäjien käyttämä idea tail-rekursiivisten funktioiden optimointiin on yksinkertainen, koska rekursiivinen kutsu on viimeinen lause, nykyisessä funktiossa ei ole enää mitään tekemistä, joten nykyisen funktion pinokehyksen tallentaminen ei ole hyödyllistä (katso tästä lisää yksityiskohdat).
Voidaanko ei-häntärekursiivinen funktio kirjoittaa häntärekursiiviseksi sen optimoimiseksi?
Tarkastellaan seuraavaa funktiota n:n kertoimen laskemiseksi.
Se on ei-tail-rekursiivinen funktio. Vaikka se näyttää ensisilmäyksellä rekursiiviselta hännältä. Jos katsomme tarkemmin, voimme nähdä, että faktan(n-1) palauttamaa arvoa käytetään tosiasia(n) . Joten kutsu tosiasia (n-1) ei ole viimeinen asia, jonka on tehnyt tosiasia(n) .
C++
#include> using> namespace> std;> // A NON-tail-recursive function. The function is not tail> // recursive because the value returned by fact(n-1) is used> // in fact(n) and call to fact(n-1) is not the last thing> // done by fact(n)> unsigned>int> fact(unsigned>int> n)> {> >if> (n <= 0)> >return> 1;> >return> n * fact(n - 1);> }> // Driver program to test above function> int> main()> {> >cout << fact(5);> >return> 0;> }> |
>
>
Java
class> GFG {> >// A NON-tail-recursive function.> >// The function is not tail> >// recursive because the value> >// returned by fact(n-1) is used> >// in fact(n) and call to fact(n-1)> >// is not the last thing done by> >// fact(n)> >static> int> fact(>int> n)> >{> >if> (n ==>0>)> >return> 1>;> >return> n * fact(n ->1>);> >}> >// Driver program> >public> static> void> main(String[] args)> >{> >System.out.println(fact(>5>));> >}> }> // This code is contributed by Smitha.> |
>
>
Python 3
# A NON-tail-recursive function.> # The function is not tail> # recursive because the value> # returned by fact(n-1) is used> # in fact(n) and call to fact(n-1)> # is not the last thing done by> # fact(n)> def> fact(n):> >if> (n>=>=> 0>):> >return> 1> >return> n>*> fact(n>->1>)> # Driver program to test> # above function> if> __name__>=>=> '__main__'>:> >print>(fact(>5>))> # This code is contributed by Smitha.> |
>
>
C#
using> System;> class> GFG {> >// A NON-tail-recursive function.> >// The function is not tail> >// recursive because the value> >// returned by fact(n-1) is used> >// in fact(n) and call to fact(n-1)> >// is not the last thing done by> >// fact(n)> >static> int> fact(>int> n)> >{> >if> (n == 0)> >return> 1;> >return> n * fact(n - 1);> >}> >// Driver program to test> >// above function> >public> static> void> Main() { Console.Write(fact(5)); }> }> // This code is contributed by Smitha> |
>
>
PHP
// A NON-tail-recursive function. // The function is not tail // recursive because the value // returned by fact(n-1) is used in // fact(n) and call to fact(n-1) is // not the last thing done by fact(n) function fact( $n) { if ($n == 0) return 1; return $n * fact($n - 1); } // Driver Code echo fact(5); // This code is contributed by Ajit ?>>> |
>
>// A NON-tail-recursive function.>// The function is not tail>// recursive because the value>// returned by fact(n-1) is used>// in fact(n) and call to fact(n-1)>// is not the last thing done by>// fact(n)>function>fact(n)>{>>if>(n == 0)>>return>1;>>>return>n * fact(n - 1);>}>// Driver code>document.write(fact(5));>// This code is contributed by divyeshrabadiya07>>>>Lähtö120>Aika monimutkaisuus: Päällä)
Aputila: Päällä)Yllä oleva funktio voidaan kirjoittaa tail-rekursiivisena funktiona. Ajatuksena on käyttää yhtä argumenttia lisää ja kerätä tekijäarvo toiseen argumenttiin. Kun n saavuttaa 0:n, palauta kertynyt arvo.
Alla on toteutus tail-rekursiivista funktiota käyttäen.
C++
#include>using>namespace>std;>// A tail recursive function to calculate factorial>unsigned factTR(unsigned>int>n, unsigned>int>a)>{>>if>(n <= 1)>>return>a;>>return>factTR(n - 1, n * a);>}>// A wrapper over factTR>unsigned>int>fact(unsigned>int>n) {>return>factTR(n, 1); }>// Driver program to test above function>int>main()>{>>cout << fact(5);>>return>0;>}>>>Java
// Java Code for Tail Recursion>class>GFG {>>// A tail recursive function>>// to calculate factorial>>static>int>factTR(>int>n,>int>a)>>{>>if>(n <=>0>)>>return>a;>>return>factTR(n ->1>, n * a);>>}>>// A wrapper over factTR>>static>int>fact(>int>n) {>return>factTR(n,>1>); }>>// Driver code>>static>public>void>main(String[] args)>>{>>System.out.println(fact(>5>));>>}>}>// This code is contributed by Smitha.>>komento chown>Python 3
# A tail recursive function># to calculate factorial>def>fact(n, a>=>1>):>>if>(n <>=>1>):>>return>a>>return>fact(n>->1>, n>*>a)># Driver program to test># above function>print>(fact(>5>))># This code is contributed># by Smitha># improved by Ujwal, ashish2021>>>C#
// C# Code for Tail Recursion>using>System;>class>GFG {>>// A tail recursive function>>// to calculate factorial>>static>int>factTR(>int>n,>int>a)>>{>>if>(n <= 0)>>return>a;>>return>factTR(n - 1, n * a);>>}>>// A wrapper over factTR>>static>int>fact(>int>n) {>return>factTR(n, 1); }>>// Driver code>>static>public>void>Main()>>{>>Console.WriteLine(fact(5));>>}>}>// This code is contributed by Ajit.>>>PHP
// A tail recursive function // to calculate factorial function factTR($n, $a) { if ($n <= 0) return $a; return factTR($n - 1, $n * $a); } // A wrapper over factTR function fact($n) { return factTR($n, 1); } // Driver program to test // above function echo fact(5); // This code is contributed // by Smitha ?>>>>
>// Javascript Code for Tail Recursion>// A tail recursive function>// to calculate factorial>function>factTR(n, a)>{>>if>(n <= 0)>>return>a;>>>return>factTR(n - 1, n * a);>}>>// A wrapper over factTR>function>fact(n)>{>>return>factTR(n, 1);>}>// Driver code>document.write(fact(5));>// This code is contributed by rameshtravel07>>>>>Lähtö120>Aika monimutkaisuus: Päällä)
Aputila: O(1)Seuraavat artikkelit tästä aiheesta:
- Tail Call eliminointi
- QuickSort Tail Call -optimointi (vähentää pahimman tapauksen tilaa lokiin n)