# 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)

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

Sort 199 Discussions, By:

Please Login in order to post a comment