News for hackers. Stuff that matters.
Re:Thinking About Recursion by chris_st on Sunday October 11, 2020 @09:17AM (#24745556)
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 :-)

Re:Thinking About Recursion by meken on Sunday October 11, 2020 @12:50PM (#24747122)
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.

Re:Thinking About Recursion by mattkrause on Sunday October 11, 2020 @08:47AM (#24745416)
Re:Thinking About Recursion by cpach on Sunday October 11, 2020 @08:59AM (#24745466)
I see what you did there…
Re:Thinking About Recursion by wa1987 on Sunday October 11, 2020 @09:38AM (#24745685)
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.

Re:Thinking About Recursion by bogomipz on Sunday October 11, 2020 @11:10AM (#24746294)
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?

Re:Thinking About Recursion by ColinWright on Sunday October 11, 2020 @11:42AM (#24746525)
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.
Re:Thinking About Recursion by Jtsummers on Sunday October 11, 2020 @12:05PM (#24746722)
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.
Re:Thinking About Recursion by formerly_proven on Sunday October 11, 2020 @12:13PM (#24746774)
> 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.

Re:Thinking About Recursion by tromp on Sunday October 11, 2020 @06:16AM (#24744814)
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.

Re:Thinking About Recursion by qsort on Sunday October 11, 2020 @06:52AM (#24744916)
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)

Re:Thinking About Recursion by oplaadpunt on Sunday October 11, 2020 @08:49AM (#24745428)
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

Re:Thinking About Recursion by qsort on Sunday October 11, 2020 @09:01AM (#24745484)
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.

Re:Thinking About Recursion by thethirdone on Sunday October 11, 2020 @09:11AM (#24745523)
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.

Re:Thinking About Recursion by dooglius on Sunday October 11, 2020 @09:06AM (#24745497)
Re:Thinking About Recursion by ColinWright on Sunday October 11, 2020 @07:03AM (#24744962)
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.

Re:Thinking About Recursion by austincheney on Sunday October 11, 2020 @07:10AM (#24744989)
Tree navigation, such as file system, is probably the best real world example off the top of my head.
Re:Thinking About Recursion by anonymoushn on Sunday October 11, 2020 @06:53AM (#24744919)
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.
Re:Thinking About Recursion by codr7 on Sunday October 11, 2020 @10:04AM (#24745850)
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.

Re:Thinking About Recursion by glandium on Sunday October 11, 2020 @06:54PM (#24749822)
Code generated with tail-call optimization is, in fact, literally a loop.
Re:Thinking About Recursion by tgv on Sunday October 11, 2020 @12:59PM (#24747210)
The recursive version of Fibonacci is generally not tail recursive, but f(n) = f(n - 1) + f(n - 2).
Re:Thinking About Recursion by codr7 on Sunday October 11, 2020 @06:36PM (#24749714)
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

Re:Thinking About Recursion by tgv on Monday October 12, 2020 @02:04AM (#24751818)
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.
Re:Thinking About Recursion by codr7 on Monday October 12, 2020 @02:56PM (#24758033)
Depends, not all languages provide variables and since they're more or less equal it's a matter of preference in other cases.
Re:Thinking About Recursion by xupybd on Sunday October 11, 2020 @04:55PM (#24749015)
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.
Re:Thinking About Recursion by newen on Sunday October 11, 2020 @04:59PM (#24749055)
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.

Re:Thinking About Recursion by skybrian on Sunday October 11, 2020 @06:09PM (#24749515)
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.

Re:Thinking About Recursion by Jtsummers on Sunday October 11, 2020 @06:18PM (#24749586)
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).
Re:Thinking About Recursion by skybrian on Sunday October 11, 2020 @06:39PM (#24749735)
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.

Re:Thinking About Recursion by Jtsummers on Sunday October 11, 2020 @07:24PM (#24749990)
That makes sense, thanks.
Re:Thinking About Recursion by xupybd on Sunday October 11, 2020 @08:29PM (#24750357)
>>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.

Re:Thinking About Recursion by lostmsu on Sunday October 11, 2020 @08:10AM (#24745241)
http://robozzle.com is a great recursion-bazed puzzle
Re:Thinking About Recursion by oumua_don17 on Sunday October 11, 2020 @11:38AM (#24746502)
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....

Re:Thinking About Recursion by seesawtron on Sunday October 11, 2020 @01:13PM (#24747330)
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

Re:Thinking About Recursion by gregfjohnson on Sunday October 11, 2020 @01:44PM (#24747586)
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..)
Re:Thinking About Recursion by cryptos on Sunday October 11, 2020 @07:42AM (#24745120)
Thinking about recursion is thinking about recursion.
Re:Thinking About Recursion by codr7 on Sunday October 11, 2020 @10:07AM (#24745871)
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.
Re:Thinking About Recursion by Jtsummers on Sunday October 11, 2020 @11:10AM (#24746290)
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.
Re:Thinking About Recursion by tromp on Sunday October 11, 2020 @07:45AM (#24745133)
I like this version:

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

Re:Thinking About Recursion by tobr on Sunday October 11, 2020 @08:25AM (#24745318)
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?
Re:Thinking About Recursion by LudwigNagasena on Sunday October 11, 2020 @09:03AM (#24745487)
Indeed, the joke seems to be more appropriate for something like “In order to understand circular reasoning, you must first understand circular reasoning.”
Re:Thinking About Recursion by logarhythmic on Sunday October 11, 2020 @08:35AM (#24745367)
The base case is understanding the joke
Re:Thinking About Recursion by joppy on Sunday October 11, 2020 @08:47AM (#24745415)
If you don’t yet understand recursion, you must first understand recursion.