Skriv en svansrekursiv funktion för att beräkna det n:te Fibonaccitalet.
Exempel:
Input : n = 4 Output : fib(4) = 3 Input : n = 9 Output : fib(9) = 34
Förutsättningar: Svansrekursion Fibonacci-siffror
En rekursiv funktion är svans rekursiv när det rekursiva anropet är det sista som exekveras av funktionen.
Att skriva en svansrekursion är lite knepigt. För att få den korrekta intuitionen tittar vi först på den iterativa metoden för att beräkna det n:te Fibonacci-talet.
int fib(int n) { int a = 0 b = 1 c i; if (n == 0) return a; for (i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return b; }
Här finns tre möjligheter relaterade till n:-
n == 0
n == 1
n > 1
De två första är triviala. Vi fokuserar på diskussion om fallet när n > 1.
I vårt iterativa tillvägagångssätt för n > 1
Vi börjar med
a = 0 b = 1
För n-1 gånger upprepar vi följande för beställt par (ab)
Även om vi använde c i faktisk iterativ metod men huvudsyftet var enligt nedan: -
(a b) = (b a+b)
Vi returnerar äntligen b efter n-1 iterationer.
Därför upprepar vi samma sak denna gång med det rekursiva tillvägagångssättet. Vi ställer in standardvärdena
a = 0 b = 1
Här kommer vi att anropa samma funktion rekursivt n-1 gånger och på motsvarande sätt ändra värdena på a och b.
Äntligen tillbaka b.
Om det är n == 0 ELLER n == 1 behöver vi inte oroa oss mycket!
Här är implementering av svans rekursiv fibonacci-kod.
// Tail Recursive Fibonacci // implementation #include
// Tail Recursive // Fibonacci implementation class GFG { // A tail recursive function to // calculate n th fibonacci number static int fib(int n int a int b ) { if (n == 0) return a; if (n == 1) return b; return fib(n - 1 b a + b); } public static void main (String[] args) { int n = 9; System.out.println('fib(' + n +') = '+ fib(n01) ); } }
# A tail recursive function to # calculate n th fibonacci number def fib(n a = 0 b = 1): if n == 0: return a if n == 1: return b return fib(n - 1 b a + b); # Driver Code n = 9; print('fib('+str(n)+') = '+str(fib(n)))
// C# Program for Tail // Recursive Fibonacci using System; class GFG { // A tail recursive function to // calculate n th fibonacci number static int fib(int n int a int b ) { if (n == 0) return a; if (n == 1) return b; return fib(n - 1 b a + b); } // Driver Code public static void Main () { int n = 9; Console.Write('fib(' + n +') = ' + fib(n 0 1) ); } } // This code is contributed // by nitin mittal.
// A tail recursive PHP function to // calculate n th fibonacci number function fib($n $a = 0 $b = 1) { if ($n == 0) return $a; if ($n == 1) return $b; return fib($n - 1 $b $a + $b); } // Driver Code $n = 9; echo 'fib($n) = ' fib($n); return 0; // This code is contributed by nitin mittal. ?> <script> // A tail recursive Javascript function to // calculate n th fibonacci number function fib(n a = 0 b = 1) { if (n == 0){ return a; } if (n == 1){ return b; } return fib(n - 1 b a + b); } // Driver Code let n = 9; document.write(`fib(${n}) = ${fib(n)}`); // This code is contributed by _saurabh_jaiswal. </script>
Utgång:
fib(9) = 34
Analys av algoritm
Time Complexity: O(n) Auxiliary Space : O(n)