# Recursion: Fibonacci Numbers

# Recursion: Fibonacci Numbers

kylemart + 5 comments O(n) time-complexity; O(1) space-complexity. Passes all cases.

public static int fibonacci(int n) { int[] fib = new int[2]; fib[0] = 0; fib[1] = 1; for (int i = 2; i <= n; ++i) { fib[i % 2] = fib[0] + fib[1]; } return fib[n % 2]; }

Gurupad + 6 comments Nice :)

Here is a one-liner in python,

fib = lambda n:pow(2<<n,n+1,(4<<2*n)-(2<<n)-1)%(2<<n) print (fib(int(input())))

Complexity :

MIC0DE + 1 comment Python one-liners are so sexy.

josediaznunez3 + 1 comment C++ one-liners are sexy, too (and rare?):

int fibonacci(int n) { return (n < 2) ? n : (fibonacci(n - 1) + fibonacci(n - 2)); }

machinekoder + 0 comments Unfortunately most oneliners suffer from unreadability.

abimamtha1998 + 0 comments please explain this problem

jae_duk_seo + 0 comments holly shit.... lambda as supre powerful...

heynemann + 0 comments Although it's curious to find a non-iterative, closed-form solution, this isn't a practical method at all. We're doing integer arithmetic with integers of size O(n2) bits, and in fact, before performing the final bit-wise and, we've got an integer that is the first n Fibonacci numbers concatenated together!

Not sure you'd want to use it, though.

adammoses + 0 comments Well done.

kcampos0101 + 0 comments [deleted]kcampos0101 + 2 comments To be picky: The problem asked for recursion :P

Gurupad + 0 comments Yep, I agree on that. Just sharing different solutions :)

phillipnguyen + 2 comments To be fair, if this were an actual interview question, I think I would want to point out that the naive recursive solution (without memoization or special formulas) is absolutely the worst way to compute Fibonacci numbers. If you draw out the call tree for say fib(10), you see that the function gets called a crazy number of times with the same values. The iterative version is just a better solution.

kcampos0101 + 1 comment but you

*can*do it recursively in O(n) time complexity with O(n) space complexityphillipnguyen + 2 comments How, without memoization or special formulas? To elaborate a bit more, here is a list of the different methods I can think of for computing the Fibonacci numbers:

- Binet's formula
- Iterative solution without memoization
- Iterative solution with memoization
- Recursive solution without memoization
- Recursive solution with memoization
- Recursive solution using formulas for F(2n) and F(2n+1) with or without memoization.

If you only plan to call the function a few times and you're not worried about possible floating point errors, then 1 is the best. If you're calling it many times, then 3 is better than 5 is better than 1. If you need to calculate really large Fibonacci numbers, then 6 is the best. Without memoization the performance of solution 4 is horrible.

kcampos0101 + 0 comments I was referring to 5. Recursive solution with memoization

dxin2 + 1 comment #include <iostream> using namespace std; void fibonacci(int n, int *fn, int *fn1) { // Complete the function. if(n==1){ *fn=1; *fn1=0; return; } int fn_, fn1_; fibonacci(n-1, &fn_, &fn1_); *fn = fn_+fn1_; *fn1 = fn_; } int main() { int n; int fn, fn1; cin >> n; fibonacci(n,&fn,&fn1); cout << fn; return 0; }

ilya_kolpakov + 0 comments Cool trick!

sr_businessemai1 + 0 comments Implementation with cache to reduce redundant calculations and help with response times.

static Map cache = new HashMap();

public static int fibonacci(int n) { if(n==0) return 0; if(n==1) return 1; if(cache.get(n) != null) return (int) cache.get(n); int a = fibonacci(n-1); int b = fibonacci(n-2); cache.put(n-1,a); return a+b; }

pjkaminsk + 0 comments Here was my idea which is similar, but easier to read/remember because it's more mechanical--the modulo math is removed, and instead an extra copy operation is used to keep the array ordered newest-to-oldest. Special case 0 and start the loop at 1.

public static int Fibonacci(int n) { if (n == 0) { return 0; } int[] answers = new int[] { 0, 1 }; for (int ii = 1; ii < n; ii++) { answers[1] = answers[0] + (answers[0] = answers[1]); } return answers[1]; }

akshay2plus + 0 comments I am not able to get this.... n%2 is either equal to 1 or 0. which means that the function will return value either 1 or 0 for any fibonacci n.

jules_penel_bba + 4 comments Here is a one liner in Python using the Golden Ratio. Faster processing guaranteed!

**Golden ratio****n-th Fibonnaci number is the closest value of:**print(round((((1+(5**0.5))/2)**int(input()))/(5**0.5)))

carsonlmh + 1 comment Awesome!

ilya_kolpakov + 0 comments Wow!

nik_roby + 0 comments Nice! I've not seen it solved this way yet.

phillipwongseven + 0 comments how accurate is this estimate formula?

nishkalavallabhi + 0 comments Wow, never knew this solution. Thanks.

zoomis_gogo + 3 comments This is my Python2 code which I've used a memory for storing existing Fibonacci number.

memory = {} def fibonacci(n): if n < 2: return n if not n in memory.keys(): memory[n] = fibonacci(n-1) + fibonacci(n-2) return memory[n]

miljanm + 0 comments nice recursion + dp

Thomas_moussajee + 1 comment You can use Exception (Try/ Catch) to make it more fast !

mem = {} def fibonacci(n): if n < 2: return n try: return mem[n] except: mem[n] = fibonacci(n - 1) + fibonacci(n - 2) return mem[n]

phillipwongseven + 1 comment How is it that dictionary are not passed recursively ?

ykurtbas + 0 comments it is in the global scope where function lives

mubarakbsc123 + 0 comments @Zoomis_gogo: Awesome solution! Great!

farrahad + 1 comment Recursion times out in python for n = 39 (test case #0). My solution is below:

def fibonacci(n): if n > 1: return fibonacci(n - 1) + fibonacci(n - 2) else: return n

jayser_mendez + 0 comments What about this:

def fibonacci(n): if n is 0 or n is 1: return n return fibonacci(n - 1) + fibonacci(n - 2)

carrickdb + 3 comments The official answer in Python times out for me.

jeanandrepf811 + 1 comment Me too; for test case #0. Do you find an error in your code or it is the test?

eneagoe + 0 comments The official answer times out in Ruby, too. Without memoization, Python and Ruby seem too slow for those levels of recursion.

TheMonkies + 0 comments Memoization fixes that issue

xiaoxia908 + 0 comments I am new to HackerRank. Is there an official answer?

Lantian + 2 comments My C++ solution. Quite straightforward.

int fibonacci(int n) { return n < 2 ? n : fibonacci(n-1) + fibonacci(n-2); }

jonjanelle1 + 0 comments This works, but will have exponential time complexity.

thippeswamydcts + 0 comments awesome. @Lantian

vernonquan + 1 comment Three different JavaScript solutions

Recursive (This is supposed to be the way we're solving it. Linear time and space complexity)

const fibonacci = (n, cache = {}) => { if (n < 0 || n === undefined) return null; if (n < 2) return n; if (cache[n]) return cache[n]; cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache); return cache[n]; };

Iterative (Better solution since it has a constant space complexity but still has linear time complexity)

const fibonacci = n => { let previous = 0; let current = 1; if (n < 0 || n === undefined) return null; if (n < 2) return n; for (let i = 1; i < n; i++) { let temp = current; current = current + previous; previous = temp; } return current; };

And Binet's formula / Golden Ratio (Super efficient constant time AND space complexity)

const fibonacci = n => { if (n < 0 || n === undefined) return null; return Math.round(Math.pow(((1 + Math.sqrt(5)) / 2), n) / Math.sqrt(5)); };

ratulbasak93 + 0 comments fibonacci = lambda x: 1 if x<=2 else fibonacci(x-1) + fibonacci(x-2)

x = int(input())

print(fibonacci(x))

ajaycarnet + 2 comments Is it too naive approach?

`public static int Fibonacci(int n) { int a = 0, b = 1, c=0; for (int i = 0; i < n-1; i++) { c = a + b; a = b; b = c; } return c; }`

alexiushaledubu1 + 0 comments Nope. This is perfect too.

shortcut2alireza + 0 comments It's just not recusrive ;)

abh_idubey011999 + 1 comment Problem with fibonacci(n-1) + fibonacci(n-2) is that it takes huge amount of time to calculate . With complexity of O(2^n) , for large values of 'n' .

iit2014063 + 0 comments you forgot about memoization

juanjosegzl + 2 comments class Fib: def __init__(self): self.memo = {0: 0, 1: 1} def fibonacci(self, n): if not n in self.memo: self.memo[n] = self.fibonacci(n-1) + self.fibonacci(n-2) return self.memo[n] n = int(raw_input()) print(Fib().fibonacci(n))

neverloseks + 0 comments using a class with memoize is a clever way..

avrodrigues5 + 0 comments Could you let me why the 1st case did not timeout?

Sort 160 Discussions, By:

Please Login in order to post a comment