ASTES REKURSIJA FIBONAČI

Uzrakstiet astes rekursīvo funkciju n-tā Fibonači skaitļa aprēķināšanai.
Piemēri:

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

Priekšnosacījumi: Astes rekursija Fibonači skaitļi
Rekursīva funkcija ir astes rekursīvs kad rekursīvais izsaukums ir pēdējā funkcija, ko izpilda funkcija.

policijas komisāra asistents

Astes rekursijas rakstīšana ir nedaudz sarežģīta. Lai iegūtu pareizo intuīciju, vispirms aplūkojam iteratīvo pieeju n-tā Fibonači skaitļa aprēķināšanai.

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

Šeit ir trīs iespējas, kas saistītas ar n : -

n == 0

n == 1

n > 1

Pirmie divi ir triviāli. Mēs koncentrējamies uz gadījuma apspriešanu, kad n > 1.
Mūsu iteratīvajā pieejā n > 1
Mēs sākam ar

a = 0 b = 1

n-1 reizes mēs atkārtojam sekojošo pasūtītajam pārim (ab)
Lai gan mēs izmantojām c faktiskajā iteratīvajā pieejā, galvenais mērķis bija šāds:

(a b) = (b a+b)

Beidzot mēs atgriežam b pēc n-1 iterācijām.
Tāpēc šoreiz atkārtojam to pašu ar rekursīvo pieeju. Mēs iestatām noklusējuma vērtības

a = 0 b = 1

Šeit mēs rekursīvi izsauksim vienu un to pašu funkciju n-1 reizes un attiecīgi mainīsim a un b vērtības.
Visbeidzot atgriezieties b.
Ja tā gadījumā n == 0 VAI n == 1, mums nav īpaši jāuztraucas!
Šeit ir astes rekursīvā Fibonači koda ieviešana.

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>

Izvade:

fib(9) = 34

Algoritma analīze

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

Izveidojiet viktorīnu