The "better" recursive solution computes fib(n) and fib(n-1) at the same time. L... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		throwawayiionqz on July 15, 2020 \| parent \| context \| favorite \| on: Data structures and algorithms I actually used whi... The "better" recursive solution computes fib(n) and fib(n-1) at the same time. Linear time recursion! `def f(n): if n<=2: return (1, 1) else: a, b = f(n-1) return (b, a+b) def fib(n): return f(n)[1]`

dotancohen on July 15, 2020 [–]

You have a bug for the case of fib(0).

throwawayiionqz on July 15, 2020 | [–]

Indeed, if you wish the sequence to be defined at 0, eru's solution is better (and appeared earlier while I was typing)

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact