РЕКУРСИЯ НА ОПАШКАТА ЗА ФИБОНАЧИ

Напишете опашка рекурсивна функция за изчисляване на n-то число на Фибоначи.
Примери:

concat java низ

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

Предпоставки: Рекурсия на опашката Числата на Фибоначи
Рекурсивна функция е опашка рекурсивна когато рекурсивното извикване е последното нещо, изпълнено от функцията.

Писането на опашна рекурсия е малко сложно. За да получим правилната интуиция, първо разглеждаме итеративния подход за изчисляване на n-то число на Фибоначи.

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

Тук има три възможности, свързани с n:-

n == 0

n == 1

n > 1

Първите две са тривиални. Ние се фокусираме върху обсъждането на случая, когато n > 1.
В нашия итеративен подход за n > 1
Започваме с

a = 0 b = 1

За n-1 пъти повтаряме следното за подредена двойка (ab)
Въпреки че използвахме c в действителния итеративен подход, но основната цел беше следната: -

бутон в центъра css

(a b) = (b a+b)

Накрая връщаме b след n-1 итерации.
Следователно повтаряме същото нещо този път с рекурсивния подход. Задаваме стойностите по подразбиране

a = 0 b = 1

Тук ще извикаме рекурсивно същата функция n-1 пъти и съответно ще променим стойностите на a и b.
Накрая се върнете b.
Ако неговият случай е n == 0 ИЛИ n == 1, не трябва да се тревожим много!
Ето изпълнението на опашния рекурсивен код на Фибоначи.

пу

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>

Изход:

fib(9) = 34

Анализ на алгоритъма

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

Създаване на тест

TechCodeview

Рекурсия на опашката за Фибоначи