Tail Recursion for Fibonacci
Write a tail recursive function for calculating the n-th Fibonacci number.
Examples :
Input : n = 4 Output : fib(4) = 3 Input : n = 9 Output : fib(9) = 34
Prerequisites : Tail Recursion, Fibonacci numbers
A recursive function is tail recursive when the recursive call is the last thing executed by the function.
Writing a tail recursion is little tricky. To get the correct intuition, we first look at the iterative approach of calculating the n-th Fibonacci number.
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; }
Here there are three possibilities related to n :-
n == 0
n == 1
n > 1
First two are trivial. We focus on discussion of the case when n > 1.
In our iterative approach for n > 1,
We start with
a = 0 b = 1
For n-1 times we repeat following for ordered pair (a,b)
Though we used c in actual iterative approach, but the main aim was as below :-
(a, b) = (b, a+b)
We finally return b after n-1 iterations.
Hence we repeat the same thing this time with the recursive approach. We set the default values
a = 0 b = 1
Here we’ll recursively call the same function n-1 times and correspondingly change the values of a and b.
Finally, return b.
If its case of n == 0 OR n == 1, we need not worry much!
Here is implementation of tail recursive fibonacci code.
C++
// Tail Recursive Fibonacci // implementation #include <iostream> 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(n, 0 , 1 ) ); } } |
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#
// 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
<?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> |
Output :
fib(9) = 34
Analysis of Algorithm
Time Complexity: O(n) Auxiliary Space : O(n)
Contact Us