フィボナッチの末尾再帰

n 番目のフィボナッチ数を計算するための末尾再帰関数を作成します。
例:

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

前提条件: 末尾再帰フィボナッチ数
再帰関数とは、末尾再帰的再帰呼び出しが関数によって最後に実行されるとき。

Inkscape vs Gimp

末尾再帰を書くのは少し難しいです。正しい直感を得るために、まず 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 に関連する 3 つの可能性があります:-

n == 0

n == 1

n > 1

最初の 2 つは簡単なことです。 n > 1 の場合の議論に焦点を当てます。
n > 1 の反復アプローチでは
から始めます

Javaの部分文字列メソッド

a = 0 b = 1

n-1 回、順序ペア (ab) について以下を繰り返します。
実際の反復アプローチでは c を使用しましたが、主な目的は次のとおりです:-

(a b) = (b a+b)

n-1 回の反復後に最終的に b を返します。
したがって、今回は再帰的アプローチで同じことを繰り返します。デフォルト値を設定します

Javaプログラミング素数

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)

クイズの作成