TAIL REKURZIÓ FIBONACCI SZÁMÁRA

Írjon egy farok rekurzív függvényt az n-edik Fibonacci-szám kiszámításához!
Példák:

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

Előfeltételek: Tail Rekurzió Fibonacci számok
A rekurzív függvény az farok rekurzív amikor a rekurzív hívás a függvény által végrehajtott utolsó dolog.

A farokrekurzió írása kicsit bonyolult. A helyes intuíció eléréséhez először nézzük meg az n-edik Fibonacci-szám kiszámításának iteratív megközelítését.

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

Itt három lehetőség van az n-hez kapcsolódóan:-

n == 0

n == 1

n > 1

Az első kettő triviális. Arra az esetre összpontosítunk, amikor n > 1.
Iteratív megközelítésünkben n > 1 esetén
Kezdjük azzal

a = 0 b = 1

n-1 alkalommal megismételjük a következőt a rendezett párnál (ab)
Bár a c-t használtuk a tényleges iteratív megközelítésben, de a fő cél a következő volt: -

(a b) = (b a+b)

Végül n-1 iteráció után visszaadjuk b-t.
Ezért ismételjük meg ugyanazt ezúttal a rekurzív megközelítéssel. Beállítjuk az alapértelmezett értékeket

a = 0 b = 1

Itt n-1 alkalommal rekurzívan meghívjuk ugyanazt a függvényt, és ennek megfelelően változtatjuk a és b értékét.
Végül térjen vissza b.
Ha az esete n == 0 VAGY n == 1, akkor nem kell sokat aggódnunk!
Itt van a farok rekurzív fibonacci kód megvalósítása.

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>

Kimenet:

fib(9) = 34

Algoritmus elemzése

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

Kvíz létrehozása

TechCodeview

Tail Rekurzió Fibonacci számára