Hacker News Reader

Comment by seanhunter | Hacker News Reader

I wish every article that wanted an example of recusion didn't immediately reach for fibbonacci or factorial, both of which are much better expressed by just calculating iteratively from the bottom and then memoizing the results for future calls. When I started to learn programming, for ages I thought recursion was just stupid because every single example I saw in a textbook could better be written without recursion.

For goodness sake if you want to write an example of recursion, walk a tree. That's a great example of a use of recursion given that the iterative version is much clumsier to express.

View on HN

Factorial was taken as an example (in this post) exactly because it is such a common textbook example, which also happens to be bad example in the sense that it is not stack-safe.

As for walking a tree, I agree, but this optimization does not work well with trees shrug, making lists a nicer example in my opinion.

As a teaching method, I feel that factorial is a relatively good example because it is fairly easy to grok in your head or on paper. Recursing through a tree adds a lot of mental overhead, so I feel like it could be a follow-up example to factorial, but it's probably too hard as an initial example. Also, switching to a stack-safe function using recursion is again much easier for factorial than it would be for traversing a tree.

Maybe this is a neurodiversity thing but for me going backwards to calculate something like a factorial recursively is hard to think about. It's exactly the same as if someone was trying to teach something about structural integrity in architecture and they said "OK you want to build a staircase. Imagine you're hovering in the air and you start to build stairs down..." I can't concentrate on whatever point they're trying to make with the example because I can't really get over the fact that it's easier to build from the bottom and not hover in the air in the first place.

Maybe try to imagine it from the architects point of view first, instead of from the brick layers? Like in an isometric drawing, for instance?

Fibonacci is better memoized because it changes an exponential time algorithm into a linear time one, but I don't see why factorial would be better memoized.

If you memoize you turn either of them into constant time. So it's an improvement to factorial (albeit less dramatic) and in practise if you later on reach for a higher factorial than you have previously calculated you don't need to start from scratch which is a real-world speedup although the O is still linear.

That said obviously the decision of whether to memoize depends on whether the function is going to be called more than once. If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods.

> If you're not calling fibbonacci more than once there is a closed form solution which is better for many input values than any of these methods.

I don't think that's true; you're pretty much always better off calculating Fibonacci numbers by starting from F_0 and counting up than by using the closed-form solution.

Are you sure? The closed form solution can be evaluated in logarithmic time whereas counting up takes linear time.

Here's an article talking about it:

https://towardsdatascience.com/why-is-the-closed-form-of-the...

It covers a couple of points (all of this is me summarizing the article I just linked; I'm not an expert in numeric computing):

- The closed-form expression for Fibonacci numbers involves an irrational number. But we can't do computations on irrational numbers; we're stuck with rational approximations. (Such as IEEE floating point.) Since computing an early Fibonacci number involves raising ϕ to a high exponent, the error involved in giving ϕ a finite representation rapidly compounds, corrupting the result. (According to this article, errors will become visible after F_100. That's quickly enough that you'd be justified in just having a lookup table for the first 100 Fibonacci numbers, which would be much faster than computing them as needed.)

- You can represent the Fibonacci recurrence relation directly in matrix form. This is just the counting-up method written down a different way. Each Fibonacci number is the product of the constant matrix [[1 1] [1 0]] with the vector consisting of the previous two Fibonacci numbers.

- You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic.

> You can exponentiate the matrix n-1 times to get a matrix that converts F_1 and F_0 (known in advance) into F_n and F_{n-1}. This is just as amenable to the shortcuts involved in calculating large exponents of a value as exponentiating ϕ is. But it's exact integer arithmetic.

Right, and repeated squaring can give you the answer to the exponentiation in logarithmic time.

> If you memoize you turn either of them into constant time.

At the risk of stumbling into the No True Memoization fallacy, I wouldn't consider that memoizing -- at least not in the dynamic programming sense. To get O(1), you're not temporarily tabling the results during a single run of the algorithm; rather you're building a semi-permanent database of answers and (effectively, in an amortized sense) discarding the algorithm altogether. I think that's formally known as the "just Google it" approach to optimization. :) From a DP perspective you can get O(N) from memoization on open-form Fibonacci, and no gain on open-form factorial, because the lookup table is ephemeral.

This is probably the most "hackernews" conversation I've ever had but as far as I've ever seen the term used, "memoization" is not restricted to temporarily tabling the results during a single run of the algorithm but used to mean any caching of results of an expensive pure function for future use. You seem to call that a "semi-permanent database of answers". Here is the original memoization paper [1] where he is using a constant-time table lookup exactly as I envisage in this case rather than only tabling results during a single invocation of the algorithm. Ironically he uses it to memoize a recursively-defined factorial function.

[1] https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash...

lol, yes, we are at Peak HN right now. :) Michie (1968) wins the debate, without a doubt! Thanks for sharing your point of view, and the article.

Reply on news.ycombinator.com