Thinking About Recursion | Hacker News Reader

Thinking About Recursion

solipsys.co.uk

65 pointsColinWright43 comments

I like to explain recursion by describing how I often write functions. I'll get to a bit where there's something complicated needed, like a loop with a lot of conditional logic. So I'll realize it's going to be complex, decide how that piece of code could be turned into a function by deciding what to send in, and what to send out, and then put that call in and finish writing the original function. Then I'll write the (so far) imaginary function which contains the complex bit.

So recursion is just realizing that I can do the complex bit by calling the current function!

Of course, this sometimes means that the function signature needs to change, to (say) include a collecting list or something. But that's the general idea.

I'm not sure if this has ever helped anyone :-)

Yeah, top-down programming is useful for understanding recursion, e.g. "wishful thinking". I think Jerry Sussman describes this beautifully in this SICP lecture snippet

https://youtu.be/amf5lTZ0UTc?t=3501

"...but since I know [the function X], by wishful thinking, will produce the simplified result, then I don't have to think about it anymore. I've used it. I've used it in a reasonable way. I will get a reasonable answer."

I didn't understand recursion too well until finishing chapter 2 of SICP.

Discussed here: https://news.ycombinator.com/item?id=24737724

I see what you did there…

Recursion never really clicked and felt intimidating until I read "How to Design Programs":

https://htdp.org/2020-8-1/Book/part_two.html

By far the greatest educational piece I've come across on this subject matter.

A sidebar in the post states:

>"It might be worth noting here that some (most?) early programming languages (specifically Fortran 77, for example) didn't allow a function to call itself - recursive calls were explicitly forbidden."

Does anybody know why this was?

Roughly speaking, return addresses were stored in a fixed location ... the idea of a stack of return frames hadn't been invented for "high performance" languages.

And it wasn't just the return addresses, often the local variables were stored in a fixed location as well. Like using the static keyword in C, but as the default (and often only) behavior.

> Does anybody know why this was?

In general, recursive calls require stack frames, which is main memory. Tail recursion is however relatively easily transformed into the equivalent while loop, which then does not consume stack frames.

Consider:

    def factorial(n):
        if n is 1: return 1
        else: return n * factorial(n - 1)

For factorial(12345), this requires 12345 stack frames, but with tail-call optimization the compiler can transform the function into something this:

    def factorial(n):
        accum = n
        while n > 1:
            n -= 1
            accum *= n
        return accum

Besides this, some older languages just didn't have a real stack. All variables would be allocated as-if they are global variables and there would be a small array of return addresses and the current index into it somewhere. Naturally, you could not nest function calls deeper than this array was long.

For Fortran the reason may be that Fortran was (and still is) used a lot for numeric code and loops lend themselves more naturally to optimization and vectorization compared to arbitrary recursion.

The three examples used to demonstrate recursion, towers of Hanoi, fibonacci, and binary search are not the most convincing ones.

All can be solved with iteration. E.g. for Hanoi:

    max = 1 << no_of_discs;
    for (x = 1; x < max; x++)
        printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);

In the case of fibonacci, the iterative solution is exponentially faster as well.

Perhaps quicksort is a better example that cannot be easily expressed with iteration.

Any algorithm can be expressed with iteration only (or recursion only, for that matter, with asymptotically no computational overhead, if you know the general method). Recursion and iteration are thinking tools first and foremost; I'd argue that those examples are the best ones precisely because most people think about those in iterative terms.

(edit: grammar)

I might be misunderstanding, but I don't think every algorithm can be expressed through iteration. I believe the Ackerman function is an example of an algorithm that can only be computed through recursion[0].

[0]: https://en.wikipedia.org/wiki/Ackermann_function

No offense but you are absolutely misunderstanding.

The Ackermann function (or rather, the family of functions with similar behavior globally known as 'ackermann') is an example of a general recursive (i.e. computable) function that is not primitive recursive. The proof that this is the case is a classical result that's part of the usual computer science curriculum, the idea being that the asymptotic growth of Ackermann is greater than the asymptotic growth of any primitive recursive function.

However, it's easy to see that you can write any recursive function iteratively; it's sufficient to allocate memory for a stack-like structure, and wrap the function body in a while loop. Recursive calls are pushes onto the stack, and returns are pops from the stack. This is exactly how compilers are able to turn recursive calls into ASM. Notice that there is no guarantee that, in general, the function will ever exit the while loop. This is inherent; it is in fact the recursive variant of the halting problem.

https://rosettacode.org/wiki/Ackermann_function#Stackless_it...

Every recursive algorithm can be expressed without recursion. You do not need recursion to simulate a Turing machine and Turing machines can compute every total recursive function.

Generally, it is easy to turn a recursive algorithm into a loop and a stack. Simulating a CPU and running compiled code is one example of running recursive programs while only using a loop.

I wrote a version of the Ackermann function in Brainfuck (a language with only while loops), but sadly I don't know where I left the program.

This Hanoi implementation moves stacks of odd sizes and even sizes to different destinations, but the spec says it should move towers of any size to the same destination.

Educational examples are rarely "real world", and anything "real world" is usually too complex to make the underlying principles clear. In quicksort, for example, any genuine example code has to deal with the partitioning code, and then the recursion aspect is swamped with the details of getting the partitioning right. Trying to avoid that by simply describing the algorithm is generally unsatisfying.

I'm going to write a follow-up post to this with a genuine real-world (well, pure maths calculation) example ... perhaps you will find that more satisfying.

Tree navigation, such as file system, is probably the best real world example off the top of my head.

The tail-recursive version of fibonacci runs just as fast as the iterative in languages with optimized tail calls.

Tree- and graph traversal is often easier to reason about using recursion from my experience.

Worst case, you can get the same effect by pushing recursive calls on a stack/queue that's consumed iteratively.

The recursive version of Fibonacci is generally not tail recursive, but f(n) = f(n - 1) + f(n - 2).

It's easy enough to convert by adding arguments for the two variables used in the iterative version:

https://github.com/codr7/liblg/blob/master/bench/fibiter.py

https://github.com/codr7/liblg/blob/master/bench/fibtail.py

The point of recursion is not recursion, but a better way to write code. Better can be more readable, less errors, whatever, but adding two parameters to the Fibonacci function for the sake of introducing tail recursion, where even iteration is more understandable, is pointless.

Depends, not all languages provide variables and since they're more or less equal it's a matter of preference in other cases.

Code generated with tail-call optimization is, in fact, literally a loop.

I was once banned from using recursion due to the complexity it added to the code. I understand the reasoning but since moving on from that position I've found the opposite to be true. There is a class of problem the benefits hugely from recursion. Not because it adds complexity but because it nicely represents the complexity that already exists in the problem.

Just try implementing merge sort to see how recursion results in simpler code. Cannot imagine how a stack data structure and a while loop is simpler than two recursive calls.

I don’t know, maybe this is just a new programmer meme. The number of programmers have supposedly doubled every five years, so I imagine internet programming discussion would be dominated by new programmers, and would have been dominated by new programmers for the last several decades.

Whether it's simpler depends on the problem. There was a programming interview question I used to use where you'd typically build a tree and print it out. I would warn people against trying to build the tree recursively because it never went well. (Printing it out was fine.)

I think part of it was that to use recursion properly in this case, you'd have to return multiple values, and that complicated things, particularly if they were using a language like Java where it's not built-in.

Why would building a tree require returning multiple values? Was this something specific to your problem statement? Typical tree insert algorithms are usually easily expressed recursively (though since they can be tail recursive, iterative versions are usually also easy to write).

It was effectively a parsing problem. When building a tree recursively, it's natural to return the finished subtree, but more information was needed to keep track of what gets parsed next. You would need to return both the result and the start of the unparsed input.

In imperative languages, parsers are often written using the fields of an object or struct to hold the parser state. But if you're just writing a single function then it becomes more natural to keep the parser state in local variables, and recursion means you don't have easy access to it.

That makes sense, thanks.

>>Whether it's simpler depends on the problem.

I couldn't agree more. One down side of recursion can be that if you need to refactor you might find recursion is no longer the better solution. Unwinding that can be a pain.

http://robozzle.com is a great recursion-bazed puzzle

The best resource [1] I have used for recursion to

1. Learn

2. Review

3. Teach

The topic on recursive data structures in linked pdf is even more fun!!!

[1] https://www.cs.cmu.edu/~15110-f12/Touretzky-Common-Lisp-ch8....

I found this python implementation on recursion to rotate images pretty mind-blowing because it was not straighforward to imagine:

https://github.com/rvizzz/rotate

Google has a nice little Easter egg if you google "recursion". (It does miss the base-case component of recursion as noted above, but still, it's good for a laugh..)

Thinking about recursion is thinking about recursion.

I like this version:

In order to understand recursion, you must first understand recursion.

I never found that joke particularly clever because it misses the significance of having a base case. So it’s just about infinite loops. Is there a version of it that includes a base case?

The base case is understanding the joke

If you don’t yet understand recursion, you must first understand recursion.

Indeed, the joke seems to be more appropriate for something like “In order to understand circular reasoning, you must first understand circular reasoning.”

There's a book out there, can't remember which; that has two index entries for recursion, both referring to the other. I always thought it was a nice touch.

K&R, The C Programming Language, does this. There may be others but this is where I first saw it and a quick google search confirmed it.

Reply on news.ycombinator.com