Fibonacci is series of numbers like 0 1 1 2 3 5… Actually its sum of previous two elements. In this article we discuss 3 method to get nth fibonacci number
#1 Using Dynamic programming
Store computed result into array so whenever next fib(.. called we are using that value. In short we can say that we are overlapping subproblems. In the below code `dp` act as memoization element, initially we have assigned dp element as -1 till n+1 time, where n denotes the desired nth fib number
// Time Complexity: O(n)+O(1)
// Space Complexity: O(n)+ O(n)
func fib(_ n: Int, _ dp: inout [Int]) ->Int {
if n <= 1 { return n }
if dp[n] != -1 {return dp[n]}
dp[n] = fib(n-1, &dp) + fib(n-2, &dp)
return dp[n]
}
var n = 5
var dp: [Int] = Array.init(repeating: -1, count: n+1)
print(fib(n, &dp))#2 Using Recursion.
// TC: 2^n
// SC: 2^n
func fib(_ n: Int) ->Int {
if n <= 1 {
return n
}
return fib(n-1) + fib(n-2)
}#3 Using single loop(Best Approach).
// TC: O(n)+O(1)
// SC: O(1)
func fib(_ n: Int) ->Int {
if n <= 1 {return n}
var prev2 = 0
var prev1 = 1
for _ in 2...n {
let curr = prev1 + prev2
prev2 = prev1
prev1 = curr
}
return prev1
}
var n = 5
print(fib(n))// print 5Question # Find fibonacci sequence up to n
import Foundation
var n1 = 0, n2 = 1, n3 = 0
func printFibonacci(_ n: Int) {
if n > 0 {
n3 = n1 + n2
n1 = n2
n2 = n3
print(n3, terminator: " ")
printFibonacci(n - 1)
}
}
let n = 9
print("Fibonacci Series: ", terminator: "")
print("0 1", terminator: " ") // printing 0 and 1
printFibonacci(n - 2) // n-2 because 2 numbers are already printed
//prints Fibonacci Series: 0 1 1 2 3 5 8 13 21