FIBONACCI IÇIN KUYRUK ÖZYINELEMESI

N'inci Fibonacci sayısını hesaplamak için bir kuyruk özyinelemeli fonksiyon yazın.
Örnekler:

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

Önkoşullar: Kuyruk Yinelemesi Fibonacci sayıları
Özyinelemeli bir fonksiyon kuyruk özyinelemeli özyinelemeli çağrı, işlev tarafından yürütülen son şey olduğunda.

karma edilebilir java

Kuyruk özyinelemesi yazmak biraz zordur. Doğru sezgiyi elde etmek için öncelikle n'inci Fibonacci sayısını hesaplamanın yinelemeli yaklaşımına bakacağız.

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

Burada n ile ilgili üç olasılık vardır: -

n == 0

n == 1

n > 1

İlk ikisi önemsiz. n > 1 olduğu durumun tartışılmasına odaklanıyoruz.
n > 1 için yinelemeli yaklaşımımızda
ile başlıyoruz

a = 0 b = 1

Sıralı (ab) çifti için n-1 kez aşağıdaki işlemi tekrarlıyoruz
Gerçek yinelemeli yaklaşımda c'yi kullanmamıza rağmen asıl amaç aşağıdaki gibiydi: -

100 üzerinden 25

(a b) = (b a+b)

Sonunda n-1 yinelemeden sonra b'yi döndürüyoruz.
Dolayısıyla aynı şeyi bu sefer özyinelemeli yaklaşımla tekrarlıyoruz. Varsayılan değerleri ayarladık

avl ağacı döndürme

a = 0 b = 1

Burada aynı fonksiyonu yinelemeli olarak n-1 kez çağıracağız ve buna göre a ve b'nin değerlerini değiştireceğiz.
Sonunda b'yi geri getirin.
Eğer n == 0 VEYA n == 1 ise fazla endişelenmemize gerek yok!
İşte kuyruk özyinelemeli fibonacci kodunun uygulanması.

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>

Çıkış:

fib(9) = 34

Algoritma Analizi

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

Test Oluştur

TechCodeview

Fibonacci için Kuyruk Özyinelemesi