Recursión de cola para Fibonacci

Escribe una función recursiva de cola para calcular el n-ésimo número de Fibonacci. 
Ejemplos: 
 

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

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

Requisitos previos: Recursividad de cola , números de Fibonacci
Una función recursiva es recursiva de cola cuando la llamada recursiva es lo último que ejecuta la función. 
 

Escribir una recursión de cola es un poco complicado. Para obtener la intuición correcta, primero observamos el enfoque iterativo de calcular el n-ésimo número 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í hay tres posibilidades relacionadas con n :- 
 

n == 0

n == 1

n > 1

Los dos primeros son triviales. Nos enfocamos en la discusión del caso cuando n > 1. 
En nuestro enfoque iterativo para n > 1, 
comenzamos con 
 

a = 0
b = 1

Para n-1 veces repetimos lo siguiente para el par ordenado (a, b) 
Aunque usamos c en un enfoque iterativo real, pero el objetivo principal era el siguiente: – 
 

(a, b) = (b, a+b)

Finalmente devolvemos b después de n-1 iteraciones.
Por lo tanto, repetimos lo mismo esta vez con el enfoque recursivo. Establecemos los valores por defecto 
 

a = 0
b = 1

Aquí llamaremos recursivamente a la misma función n-1 veces y, en consecuencia, cambiaremos los valores de a y b. 
Finalmente, regresa b.
Si es el caso de n == 0 O n == 1, ¡no debemos preocuparnos mucho!
Aquí está la implementación del código fibonacci recursivo de cola. 
 

// Tail Recursive Fibonacci
// implementation
#include <iostream>
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;
}

// 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(n,0,1) );
    }
}

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

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

Producción : 
 

fib(9) = 34

Análisis de Algoritmo 
 

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

Este artículo es una contribución de Pratik Chhajer . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.