News for hackers. Stuff that matters.

A comment on Data structures and algorithms I actually used while working at tech companies. Parent comment

Re:Data structures and algorithms I actually used while work... by throwawayiionqz on Wednesday July 15, 2020 @07:22AM (#23843683)
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]
[ Parent | on HN ]
Re:Data structures and algorithms I actually used while work... by dotancohen on Wednesday July 15, 2020 @07:30AM (#23843741)
You have a bug for the case of fib(0).
[ Parent | on HN ]
Re:Data structures and algorithms I actually used while work... by throwawayiionqz on Wednesday July 15, 2020 @07:34AM (#23843771)
Indeed, if you wish the sequence to be defined at 0, eru's solution is better (and appeared earlier while I was typing)
[ Parent | on HN ]