4 ms·
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 iterat
by tromp 6y ago
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.
- qsort 6y agoAny 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)
- oplaadpunt 6y agoI 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 https://en.wikipedia.org/wiki/Ackermann_function
- qsort 6y agoNo 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.
- dooglius 6y agohttps://rosettacode.org/wiki/Ackermann_function#Stackless_iterative_solution_with_multiple_precision.2C_fast https://rosettacode.org/wiki/Ackermann_function#Stackless_it...
- thethirdone 6y agoEvery 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.
- deleted 6y ago[deleted]
- anonymoushn 6y agoThis 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.
- ColinWright 6y agoEducational 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.
- austincheney 6y agoTree navigation, such as file system, is probably the best real world example off the top of my head.
- codr7 6y agoThe 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.
- tgv 6y agoThe recursive version of Fibonacci is generally not tail recursive, but f(n) = f(n - 1) + f(n - 2).
- codr7 6y agoIt'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/fibiter.py https://github.com/codr7/liblg/blob/master/bench/fibtail.py https://github.com/codr7/liblg/blob/master/bench/fibtail.py
- tgv 6y agoThe 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.
- codr7 6y agoDepends, not all languages provide variables and since they're more or less equal it's a matter of preference in other cases.
- glandium 6y agoCode generated with tail-call optimization is, in fact, literally a loop.