CO JE REKURZE OCASU - TECHCODEVIEW.COM

Rekurze ocasu je definována jako rekurzivní funkce, ve které je rekurzivní volání posledním příkazem, který je funkcí proveden. Po volání rekurze tedy v podstatě nezbývá nic k provedení.

Například následující funkce print() v C++ je rekurzivní.

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>

Jáva

// 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>

Python3

# 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> >

Časová náročnost: Na)
Pomocný prostor: Na)

Potřeba rekurze ocasu:

Koncové rekurzivní funkce jsou považovány za lepší než nekoncové rekurzivní funkce, protože tail-rekurze může být optimalizována kompilátorem.

Kompilátory obvykle provádějí rekurzivní procedury pomocí a zásobník . Tento zásobník se skládá ze všech příslušných informací, včetně hodnot parametrů, pro každé rekurzivní volání. Když je procedura volána, její informace jsou tlačil do zásobníku, a když funkce skončí, informace je prasklo ze zásobníku. Tedy pro non-tail-rekurzivní funkce, hloubka zásobníku (maximální množství místa zásobníku využitého kdykoli během kompilace) je více.

Myšlenka používaná kompilátory k optimalizaci koncových rekurzivních funkcí je jednoduchá, protože rekurzivní volání je posledním příkazem, v aktuální funkci již není co dělat, takže ukládání rámce zásobníku aktuální funkce je k ničemu (další informace naleznete zde podrobnosti).

Lze nerekurzivní funkci zapsat jako koncovou rekurzivní, aby se optimalizovala?

Zvažte následující funkci pro výpočet faktoriálu n.

Je to non-tail-rekurzivní funkce. I když to na první pohled vypadá jako rekurzivní ocas. Pokud se podíváme blíže, můžeme vidět, že hodnota vrácená faktem (n-1) je použita v fakt(n) . Takže volání fakt(n-1) není to poslední, co se dělá fakt(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;> }>

Jáva

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.>

Python3

# 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 ?>>

Javascript

> // 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> >

Výstup

Časová náročnost: Na)
Pomocný prostor: Na)

Výše uvedenou funkci lze zapsat jako koncovou rekurzivní funkci. Cílem je použít ještě jeden argument a akumulovat faktoriál ve druhém argumentu. Když n dosáhne 0, vraťte akumulovanou hodnotu.

Níže je implementace pomocí tail-rekurzivní funkce.

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

Jáva

// 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.>

Python3

# 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

> // 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> > >

Výstup

Časová náročnost: Na)
Pomocný prostor: O(1)

Další články na toto téma: