Hacker News Reader

Comment by DeathArrow | Hacker News Reader

I see nothing wrong with either factorial or Fibonacci numbers.

The author argues that nobody uses or needs neither factorial nor Fibonacci numbers.

But that is not the point. If you are going to teach a concept it's best to use easy to understand examples. And factorial Fibonacci numbers are just that. I rather use factorial to teach recursion than QuickSort using Hoare partition algorithm.

And if it comes about teaching I think it is very important to so teach tail call recursion and to teach when to use recursion. Because it can be a waste to use recursion if an easy to implement iterative solution exists.

View on HN

This might be the root of the problem for the author:

>>> In principle, natural numbers are also recursive data: a number is either zero or the successor of another natural number. However, this way of thinking is not natural to students...

That's because students didn't learn math. "Back in my day," we learned mathematical induction sometime in middle school, and were re-introduced to it from time to time as a style of proof. When I finally got a chance to learn programming (in 1981), recursion was taught as something we already knew, being related to induction.

Which is closer to how it should be taught.

The factorial example is trivial and too familiar. It's easy for students to think "Oh, I know that" when in fact they don't get it at all.

Recursive operations on data structures are more likely to be unfamiliar. And you need something unfamiliar to demonstrate the point and also illustrate how it's likely to be used in practice.

Induction isn't recursion. Induction is why recursion works.

Unless you are assuming ZFC, which is much more comlplex then recursion itself, in second-order logic Induction is an axiom that we use to avoid recursion, by setting up the recursive step and then saying "so we don't have to execute it and look further"

Constructing the naturals is dynamic programming (building up), not recursion (breaking down).

Calculatiny addition using Peano axioms, that is recursion.

We hadn't gotten to those kinds of concepts in school by the time I learned recursion. The math that confounds programmers is much more basic.

Most of the time a sequence of numbers is recursively defined. Ex. Xn = Xn-1 + 2n

So a student might be familiar with it.

It was counterproductive for me when recursion was taught with Fibonacci and factorials. They were literally the opposite of easy to understand for me, I had absolutely no idea why those examples actually worked, so I just gave up and treated them like magic.

I think recursion should be taught with examples that would be easier for a student to write with recursion than without it. For example, listing all files in a directory.

Why would you think enumerating a directory is not magic?

Walking a tree / BFS is quite easy to implement iteratively, using a search queue. It's a common example for teaching Lisp.

Recursion is most natural in problems like implementing evaluation of an abstract syntax trer:

    eval(tree) = 
      apply(node(tree), 
            map(eval, leaves(tree))
           )

And since a tree is a graph, you can just use adjacency matrix and two loops. :)

O(n^2) but very simple.

That would require OS specific APIs which are distracting.

I would agree with the author that there are other, more useful examples of recursion. He gave a family tree example but for me ‘list all files on your hard disk’ would be a better example.

Tail call recursion is interesting, but that belongs in an FP course, which is usually taught long after the basics of programming.

I completely agree with this. The trouble also is that "real" recursive problems tend to be _very_ hard: an example from physics would be magnetohydrodynamics where a plasma moves in accordance to an applied external B field, causing a current to flow, which generates a B field that changes how the plasma flows...you get the idea.

Everyone knows that you don't _really_ want to try doing 123! using your "my first recursion" code in C. Similarly everyone knows that factorial gets pretty big pretty quickly – I remember finding out the limits of calculators in school by finding at which point x! went from "big number" to "error". It's pedagogically useful for those things and you can see (a) if your answer is right, compared to a BigNum library, and (b) how long it takes. There's a whole can of worms you can go down, from Sterling's approximation to a discussion about time complexity, ints and IEEE 754, and stack overflows. You could then go waffling about, e.g. Haskell and lazy evaluation and functional programming and so on.

Factorial isn't a good problem but it's common enough that students will have heard of it, deep enough to be interesting, and used so frequently as a programming example that if you see a recursive definition of factorial in another programming language you get that they're trying to teach you about recursion. It's a good teaching tool for all those reasons.

i think the problem is that most people try to follow the recursions in their head which is hard.

the biggest lesson regarding recursion is that if you're lucky enough to have your problem fit with tco (or have guarantees your problem is small enough), it's actually way simpler to both write and verify. write the base case, write the inductive step, translate to code, done. no hard reasoning about the code required because math. fact and fib demonstrate this nicely.

would prefer if programming languages offered a recursive decorator that would cause compilation or linting failures if tco isn't possible though.

>i think the problem is that most people try to follow the recursions in their head which is hard.

It's hard for computers, too as it can easy result in stack overflow if there are too many steps.

that's the obvious issue. another less intuitive one is that modern cpus and compilers are essentially optimized for iterative algorithms. state variables can be kept in registers, simd can be used for data that appears in contiguous arrays, caching is built on locality assumptions and data locality is preserved.

non-flattened recursive algorithms spread their state across linear memory with a full stack frame for every iteration. at the least this defeats gains from caches, at worst it defeats them entirely by filling them with junk.

but, if the problem is small enough it can be worth it for the correctness guarantees and increased simplicity.

trivial iterative algorithms are simpler, sure, but when things get more complicated, recursion can replace very hard to understand, test and debug iterative code with simple recursive definitions where guarantees of correctness and termination come for free.

If you go with a continuous passing style (which more often than not is relatively "easy") the compiler usually optimize it to replacing/reusing the frame rather than allocating a new one.

so it turns out that optimization is also tco (tail call optimization). that said, i was previously unfamiliar with continuous passing style, thanks!

Agree. You could use the argument that argument against almost any teaching example. Like, when's the last time you ever needed to integrate x from 0 to 1? I've never needed to do that. Or when is the last time you needed to know how long a 1 kg ball will take to fall from 1 m? At least in my opinion, the way the author thinks recursion should be taught seems to needlessly complicate it.

I've done a few integrals of x from zero to one, they come up quite a bit if x is normalized.

Exception proves the rule, though ;-)

Reply on news.ycombinator.com