Recursion Approach to Find and Print Nth Fibonacci Numbers

Dynamic Programming Approach to Find and Print Nth Fibonacci Numbers:

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation: with seed values and and .

The Nth Fibonacci Number can be found using the recurrence relation shown above:

if n = 0, then return 0.
If n = 1, then it should return 1.
For n > 1, it should return F_n-1 + F_n-2

Below is the implementation of the above approach:

C++

// Fibonacci Series using Recursion
#include <bits/stdc++.h>
using namespace std;
 
int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
 
int main()
{
    int n = 9;
    cout << n << "th Fibonacci Number: " << fib(n);
    return 0;
}
 
// This code is contributed
// by Akanksha Rai

C

// Fibonacci Series using Recursion
#include <stdio.h>
int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}
 
int main()
{
    int n = 9;
    printf("%dth Fibonacci Number: %d", n, fib(n));
    return 0;
}

Java

// Fibonacci Series using Recursion
import java.io.*;
class fibonacci {
    static int fib(int n)
    {
        if (n <= 1)
            return n;
        return fib(n - 1) + fib(n - 2);
    }
 
    public static void main(String args[])
    {
        int n = 9;
        System.out.println(
            n + "th Fibonacci Number: " + fib(n));
    }
}
/* This code is contributed by Rajat Mishra */

Python3

# Fibonacci series using recursion
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)
 
 
if __name__ == "__main__":
    n = 9
    print(n, "th Fibonacci Number: ")
    print(fibonacci(n))
 
 # This code is contributed by Manan Tyagi.

C#

// C# program for Fibonacci Series
// using Recursion
using System;
 
public class GFG {
    public static int Fib(int n)
    {
        if (n <= 1) {
            return n;
        }
        else {
            return Fib(n - 1) + Fib(n - 2);
        }
    }
 
    // driver code
    public static void Main(string[] args)
    {
        int n = 9;
        Console.Write(n + "th Fibonacci Number: " + Fib(n));
    }
}
 
// This code is contributed by Sam007

Javascript

// Javascript program for Fibonacci Series
// using Recursion
 
function Fib(n) {
  if (n <= 1) {
    return n;
  } else {
    return Fib(n - 1) + Fib(n - 2);
  }
}
 
// driver code
let n = 9;
console.log(n + "th Fibonacci Number: " + Fib(n));

PHP

<?php
// PHP program for Fibonacci Series
// using Recursion
 
function Fib($n)
{
    if ($n <= 1) {
        return $n;
    }
    else {
        return Fib($n - 1) + Fib($n - 2);
    }
}
 
// driver code
$n = 9;
echo $n . "th Fibonacci Number: " . Fib($n);
 
// This code is contributed by Sam007
?>

Output

Time Complexity: Exponential, as every function calls two other functions.
Auxiliary space complexity: O(n), as the maximum depth of the recursion tree is n.

Nth Fibonacci Number

Given a number n, print n-th Fibonacci Number.

The Fibonacci numbers are the numbers in the following integer sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ……..

Examples:

Input : n = 1

Output : 1

Input : n = 9

Output : 34

Input : n = 10

Output : 55

with seed values and

and

C++

// Fibonacci Series using Space Optimized Method
#include <bits/stdc++.h>
using namespace std;
 
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;
}
 
// Driver code
int main()
{
    int n = 9;
 
    cout << fib(n);
    return 0;
}
 
// This code is contributed by Code_Mech

C

// Fibonacci Series using Space Optimized Method
#include <stdio.h>
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;
}
 
int main()
{
    int n = 9;
    printf("%d", fib(n));
    getchar();
    return 0;
}

Java

// Java program for Fibonacci Series using Space
// Optimized Method
public class fibonacci {
    static int fib(int n)
    {
        int a = 0, b = 1, c;
        if (n == 0)
            return a;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
 
    public static void main(String args[])
    {
        int n = 9;
        System.out.println(fib(n));
    }
};
 
// This code is contributed by Mihir Joshi

Python3

# Function for nth fibonacci number - Space Optimisation
# Taking 1st two fibonacci numbers as 0 and 1
 
 
def fibonacci(n):
    a = 0
    b = 1
    if n < 0:
        print("Incorrect input")
    elif n == 0:
        return a
    elif n == 1:
        return b
    else:
        for i in range(2, n+1):
            c = a + b
            a = b
            b = c
        return b
 
# Driver Program
 
 
print(fibonacci(9))
 
# This code is contributed by Saket Modi

C#

// C# program for Fibonacci Series
// using Space Optimized Method
using System;
 
namespace Fib {
public class GFG {
    static int Fib(int n)
    {
        int a = 0, b = 1, c = 0;
 
        // To return the first Fibonacci number
        if (n == 0)
            return a;
 
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
 
        return b;
    }
 
    // Driver function
    public static void Main(string[] args)
    {
 
        int n = 9;
        Console.Write("{0} ", Fib(n));
    }
}
}
 
// This code is contributed by Sam007.

Javascript

<script>
 
// Javascript program for Fibonacci Series using Space Optimized Method
 
function fib(n)
{
    let 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;
}
 
// Driver code
 
    let n = 9;
     
    document.write(fib(n));
 
// This code is contributed by Mayank Tyagi
 
</script>

PHP

<?php
// PHP program for Fibonacci Series 
// using Space Optimized Method
 
function fib( $n)
{
    $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;
}
 
// Driver Code
$n = 9;
echo fib($n);
 
// This code is contributed by anuj_67.
?>

Output

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

Tags:

#Amazon #Bloomberg #Fibonacci #MakeMyTrip #MAQ Software #matrix-exponentiation #Modular Arithmetic #series #Snapdeal #DSA #Dynamic Programming #Mathematical #Amazon #Bloomberg #MakeMyTrip #MAQ Software #Snapdeal #Dynamic Programming #Fibonacci #Mathematical #Modular Arithmetic #series

Dynamic Programming Approach to Find and Print Nth Fibonacci Numbers:

Recursion Approach to Find and Print Nth Fibonacci Numbers

C++

C

Java

Python3

C#

Javascript

PHP

Nth Fibonacci Number

C++

C

Java

Python3

C#

Javascript

PHP

Similar Reads

Contact Us