RECURS DE LA CUA PER A FIBONACCI

Escriu una funció recursiva de cua per calcular l'enèsimo nombre de Fibonacci.
Exemples:

Input : n = 4 Output : fib(4) = 3 Input : n = 9 Output : fib(9) = 34

Requisits previs: Recurs de cua Nombres de Fibonacci
Una funció recursiva és cua recursiva quan la crida recursiva és l'última cosa que executa la funció.

Escriure una recursivitat de la cua és poc complicat. Per obtenir la intuïció correcta, primer ens fixem en l'enfocament iteratiu del càlcul del nombre n-è de Fibonacci.

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

Aquí hi ha tres possibilitats relacionades amb n:-

n == 0

n == 1

n > 1

Els dos primers són trivials. Ens centrem en la discussió del cas quan n > 1.
En el nostre enfocament iteratiu per a n > 1
Comencem amb

un milió en xifres

a = 0 b = 1

Durant n-1 vegades repetim el següent per a la parella ordenada (ab)
Tot i que vam utilitzar c en un enfocament iteratiu real, però l'objectiu principal era el següent:

(a b) = (b a+b)

Finalment tornem b després de n-1 iteracions.
Per tant, repetim el mateix aquesta vegada amb l'enfocament recursiu. Establem els valors per defecte

a = 0 b = 1

Aquí trucarem recursivament a la mateixa funció n-1 vegades i, en conseqüència, canviarem els valors de a i b.
Finalment torna b.
Si el seu cas és n == 0 O n == 1, no hem de preocupar-nos gaire!
Aquí hi ha la implementació del codi de Fibonacci recursiu de la cua.

C++

// Tail Recursive Fibonacci // implementation #include    using namespace std; // A tail recursive function to // calculate n th fibonacci number int fib(int n int a = 0 int b = 1) {  if (n == 0)  return a;  if (n == 1)  return b;  return fib(n - 1 b a + b); } // Driver Code int main() {  int n = 9;  cout << 'fib(' << n << ') = '  << fib(n) << endl;  return 0; }

Java

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

Python3

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

PHP

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

JavaScript

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

Sortida:

fib(9) = 34

Anàlisi de l'algoritme

Time Complexity: O(n) Auxiliary Space : O(n)

Crea un qüestionari

TechCodeview

Recurs de la cua per a Fibonacci