Fibonacci Number

Definition

Definition

The Fibonacci number algorithm generates a sequence of numbers known as the Fibonacci sequence, where each number is the sum of the two preceding ones, starting with 0 and 1

Explanation

To compute the nth Fibonacci number, a function named fibonacci is created, accepting an integer parameter n. Inside this function, a base case is established: if n is 0 or 1, the function returns n. Otherwise, the function recursively calls itself with n - 1 and n - 2, adding their results together. This recursive process continues until reaching the base case. Finally, the sum obtained from these recursive calls is returned as the nth Fibonacci number

Guidance

• Start with a = 0 and b = 1
• Iterate n times (where n is the desired Fibonacci number's position)
  • update temp to a
  • set a to b
  • update b to temp + b
• Return the value of a

Tips

• use dynamic programming for better efficiency
• avoid recursive approaches for large values of n due to stack overflow

Practice

Practice

fibonacci(n):
  if n <= 1:
    return n
  else:
    return fibonacci(n - 1) + fibonacci(n - 2)

Solution

package main

// Recursive
func fibonacciRecursive(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacciRecursive(n-1) + fibonacciRecursive(n-2)
}

// Iterative
func fibonacciIterative(n int) int {
    if n <= 1 {
        return n
    }
    a, b := 0, 1
    for i := 2; i <= n; i++ {
        a, b = b, a+b
    }
    return b
}

public class Fibonacci {

  // Recursive
  public static int fibonacciRecursive(int n) {
    if (n <= 1) {
      return n;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
  }

  // Iterative
  public static int fibonacciIterative(int n) {
    if (n <= 1) {
      return n;
    }
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
      int temp = b;
      b = a + b;
      a = temp;
    }
    return b;
  }
}

// Recursive
function fibonacciRecursive(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// Iterative
function fibonacciIterative(n) {
  if (n <= 1) {
    return n;
  }
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    let temp = b;
    b = a + b;
    a = temp;
  }
  return b;
}

// Recursive
fun fibonacciRecursive(n: Int): Int {
    return if (n <= 1) n else fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
}

// Iterative
fun fibonacciIterative(n: Int): Int {
    if (n <= 1) return n
    var a = 0
    var b = 1
    var temp: Int
    for (i in 2..n) {
        temp = b
        b += a
        a = temp
    }
    return b
}

# Recursive
def fibonacciRecursive(n):
    if n <= 1:
        return n
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)

# Iterative
def fibonacciIterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

// Recursive
fn fibonacci_recursive(n: i32) -> i32 {
    if n <= 1 {
        n
    } else {
        fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
    }
}

// Iterative
fn fibonacci_iterative(n: i32) -> i32 {
    if n <= 1 {
        return n;
    }
    let mut a = 0;
    let mut b = 1;
    for _ in 2..=n {
        let temp = b;
        b += a;
        a = temp;
    }
    b
}

// Recursive
function fibonacciRecursive(n: number): number {
  if (n <= 1) return n;
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

// Iterative
function fibonacciIterative(n: number): number {
  if (n <= 1) return n;
  let a = 0,
    b = 1;
  for (let i = 2; i <= n; i++) {
    let temp = b;
    b = a + b;
    a = temp;
  }
  return b;
}