Solution For Fibonacci Number

Problem Description:

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n – 1) + F(n – 2), for n > 1.
Given n, calculate F(n).

Solution:

The Fibonacci series can be solved using recursion or a iterative method. In both cases, we start by checking if the given input n is either 0 or 1. Because the Fibonacci sequence starts with 0 and 1, another base case will be when the input is either 0 or 1 that is the output will be the same as the input. This is because F(0) = 0 and F(1) = 1.

Recursive Method

In the recursive solution, we calculate the nth number in the sequence by adding the (n-1)th term and the (n-2)th term. We perform this operation until we get F(0) and F(1), which we know their values. The recursive function call continues until the base cases are reached, then it returns the sum to the previous call, which will then add its corresponding sum.

def fib(n):
if n == 0: # Base case
return 0
elif n == 1: # Base case
return 1
else:
return fib(n-1) + fib(n-2)

Iterative Method

In an iterative solution, we loop through from 0 to n, and at each iteration, we add the sum of the two previous values. The loop continues until we reach the nth number in the sequence. We use two variables to keep track of the previous numbers.

def fib(n):
if n == 0: # Base case
return 0
elif n == 1: # Base case
return 1
else:
prev_prev = 0 # F(0)
prev = 1 # F(1)
for _ in range(2,n+1):
current = prev_prev + prev
prev_prev = prev
prev = current
return current

Time and Space Complexity:

For the recursive implementation, the time complexity is O(2^n) and the space complexity is O(n). This is because the recursive function calls itself twice for each value of n.

For the iterative implementation, the time complexity is O(n) and the space complexity is O(1). This is because we only loop through the values of n, and keep track of two variables.You can use any of the two methods based on the requirements of the problem.

This problem is solved now!

Step by Step Implementation For Fibonacci Number

class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }
        return fib(N - 1) + fib(N - 2);
    }
}

// This is a simple recursive solution to the Fibonacci problem. We return the Nth Fibonacci number by first checking if N is 0 or 1. If it is, we simply return N. Otherwise, we return the sum of the two previous Fibonacci numbers.

def fib(N):
    if N <= 1:
        return N
    else:
        return fib(N-1) + fib(N-2)

// Solution 1: Recursive

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// Solution 2: Iterative

function fibonacci(n) {
  let a = 0,
    b = 1;
  for (let i = 0; i < n; i++) {
    let temp = a;
    a = b;
    b = temp + b;
  }
  return a;
}

int fib(int N) {
    if (N <= 1) {
        return N;
    }
    return fib(N - 1) + fib(N - 2);
}

using System; 

public class Solution {
    public int Fib(int N) {
        if (N <= 1) {
            return N; 
        }
        
        return Fib(N - 1) + Fib(N - 2); 
    }
}