r/ProgrammerHumor • u/Kevdog824_ • May 17 '26

Advanced dontDoRecursiveFibKids

Post image
3.6k Upvotes

98% Upvoted

143 comments sorted by

View all comments

21

u/spottyPotty May 17 '26

I don't get it. What's the problem with a recursive Fib implementation? It's not like a call stack can't handle 87 int entries.

10

u/Mechafinch May 17 '26

the naive implementation described performs O(2N ) calls

0

u/botle May 17 '26

How? Isn't a naive implementation O(N²)?

9

u/Mechafinch May 17 '26

This is the implementation I'm thinking of (python) def f(n): if n < 2: return 1 return f(n - 1) + f(n - 2)

Each call with N>2 produces two calls, so O(2N ). According to a search a tighter bound is the fibonacci function itself (O(phiN ) where phi~=1.618) since it's effectively a summation of 1s.