Timeline for Is there anything that can be done with recursion that can't be done with loops?
Current License: CC BY-SA 3.0
45 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 4, 2021 at 17:18 | comment | added | That Realtor Programmer Guy | A loop is a self-recalling block of code. Loops are recursion with defined exit conditions | |
| Nov 28, 2015 at 19:37 | comment | added | biziclop | For me, the main conceptual difference between recursion and looping is that recursion expresses locality. In recursion the result of each step only depends on its input and the result of anything called by that step. A loop on the other hand requires non-local state, shared by every iteration. The result of each iteration depends on the input and the result of all the iterations preceding it. | |
| Nov 27, 2015 at 11:46 | comment | added | Rajesh Dixit | I dont have enough points to write an answer, so adding a comment. A task that needs to run in specific interval, you can achieve using recursion but will be difficult using loops. You can check following Fiddle for reference. | |
| Nov 27, 2015 at 6:37 | answer | added | Gulshan | timeline score: 0 | |
| Nov 25, 2015 at 10:28 | answer | added | BЈовић | timeline score: 1 | |
| Nov 25, 2015 at 0:22 | comment | added | David Hammen | @WizardOfMenlo - Regarding the Ackermann function, what you wrote is not true. Writing that in a recursive language of choice and in FORTRAN and in assembly (sans recursion) was an assignment in a comparative languages class I took ages and ages ago. The recursive implementation can be a one liner. For example, def a(x,y):return y+1 if x==0 else a(x-1,1) if y==0 else a(x-1,a(x,y-1)). The non-recursive implementations were a mess, but it can be done. | |
| Nov 25, 2015 at 0:15 | comment | added | user541686 | "Prettier" is a technical term...? | |
| Nov 24, 2015 at 22:09 | comment | added | Gilles 'SO- stop being evil' | Beware that this question has attracted many answers that are mediocre or downright wrong, yet have a very high score. I recommend asking questions that require some knowledge of computer science on Computer Science rather than here. | |
| Nov 24, 2015 at 12:07 | comment | added | jcora | A much better question would be if there are things which can be done via looping and can't with recursion... | |
| Nov 24, 2015 at 11:05 | answer | added | user541686 | timeline score: 9 | |
| Nov 24, 2015 at 6:09 | answer | added | jpa | timeline score: 2 | |
| Nov 24, 2015 at 3:44 | comment | added | maple_shaft♦ | Comments are not for extended discussions. Please use the chat room if you wish to continue your discussion. Thank you. | |
| Nov 23, 2015 at 22:29 | comment | added | GargantuChet | Yes, when the concept is used as a heuristic to evaluate a programmer's understanding of the machine. The barrier for understanding loops is a bit lower. Quoting Joel Spolsky, "If I may be so brash, it has been my humble experience that there are two things traditionally taught in universities as a part of a computer science curriculum which many people just never really fully comprehend: pointers and recursion" (joelonsoftware.com/articles/ThePerilsofJavaSchools.html). | |
| Nov 23, 2015 at 21:53 | comment | added | JB King | stackoverflow.com/questions/10742322/… has an implementation of Ackermann that isn't recursive. | |
| Nov 23, 2015 at 19:56 | comment | added | Mason Wheeler | @Pinoniq To understand recursion, you must first understand recursion. | |
| Nov 23, 2015 at 18:28 | comment | added | Drathier | So many wrong answers. The ackermann function is designed as a counter-example to this. | |
| Nov 23, 2015 at 17:39 | comment | added | poshest | In async runtimes (eg javascript), you can't use a loop that involves any async call and expect the loop to resume after the async call returns. Eg using setTimeout to increment the seconds each second on a digital clock application. But recursion works a charm. Would have done this as an answer, but I don't have the reputation yet apparently. :P | |
| Nov 23, 2015 at 15:25 | comment | added | R.. GitHub STOP HELPING ICE | In most languages, the one thing recursion can do that you can't do with loops is make your program crash with no way to catch or report the error. | |
| Nov 23, 2015 at 14:40 | comment | added | recursion.ninja | Maintaining clarity while traversing a recursive structure... | |
| Nov 23, 2015 at 13:13 | answer | added | Jon Hanna | timeline score: 21 | |
| Nov 23, 2015 at 4:48 | comment | added | djechlin | Well there's lots of answers already... but I think the bottom line is there is one thereotical cs interpretation of this question where the answer is provably "yes" and another where the answer is provably "no". | |
| Nov 23, 2015 at 3:00 | comment | added | user207421 | Unless the loop also includes a stack it can hardly do anything interesting that recursion can do. | |
| Nov 23, 2015 at 0:03 | comment | added | Mark Rogers | Recursion should be used sparingly because it becomes complex to unpack the logic for the first time, and is thus less readable. Also changing the logic can become a rubix cube style puzzle, better to generally avoid it, except when doing obvious and simple node traversal. | |
| Nov 22, 2015 at 22:23 | comment | added | user40980 | @WizardOfMenlo the befunge code is a implementation of the ERRE solution (which is also an interactive solution... with a stack). An iterative approach with a stack can emulate a recursive call. On any programming that is suitably powerful, one looping construct can be used to emulate another one. The register machine with the instructions INC (r), JZDEC (r, z) can implement a Turing machine. It has no 'recursion' - thats a Jump if Zero else DECrement. If the Ackermann function is computable (it is), that register machine can do it. | |
| Nov 22, 2015 at 22:13 | comment | added | WizardOfMenlo | @MichaelT Oh, that's interesting... I thought that the Ackermann function was not a primitive recursive, and as such it couldn't be de-recursified, are you sure that it doesn't simply print the results without going through the function? Or that the Befunge code is emulating recursion (possibly)? Otherwise this leaves me quite puzzled :) | |
| Nov 22, 2015 at 22:06 | comment | added | user40980 | @WizardOfMenlo glance at Rosetta Code and then pick one of the Esolangs. Like Befunge-93: Since Befunge-93 doesn't have recursive capabilities we need to use an iterative algorithm. and note that it does it. | |
| Nov 22, 2015 at 21:12 | comment | added | WizardOfMenlo | What about Ackermann function? en.wikipedia.org/wiki/Ackermann_function, not particularly useful but impossible to do via looping. (You may also want to check this video youtube.com/watch?v=i7sm9dzFtEI by Computerphile) | |
| Nov 22, 2015 at 20:18 | history | protected | CommunityBot | ||
| Nov 22, 2015 at 17:15 | history | edited | user40980 | edited tags | |
| Nov 22, 2015 at 15:24 | comment | added | hyde | @LightnessRacesinOrbit To my non-native-English-speaker ear, "Recursion is a glorified loop" sounds you mean "You might as well use a looping construct instead of recursive call anywhere, and the concept doesn't really deserve it's own name". Perhaps I interpret the "glorified something" idiom wrong, then. | |
| Nov 22, 2015 at 15:10 | comment | added | hyde | @LightnessRacesinOrbit I was picking on "glorified something" idiom (a dismissive, pejorative expression in English), which I'd say is unfair, since recursion both demands something extra (a stack) over just being able to do looping, and enables certain kind of algorithms as a trade-off. | |
| Nov 22, 2015 at 14:43 | comment | added | Lightness Races in Orbit | @hyde: "without emulating recursion" That introduces a circular argument! If we're to use the "fact" that recursion is a glorified loop to rewrite a recursive algorithm in a loop, then of course the logic is going to be extremely similar, with the addition of our own stack for data storage. I agree that logically it'll look pretty much the same, and that's kind of my point. | |
| Nov 22, 2015 at 14:21 | comment | added | hyde | @LightnessRacesinOrbit "glorified loop" is a bit harsh. Try implementing reasonable general O(NlogN) sorting algorithm with loop and without emulating recursion, why which I mean having your own stack which does same thing as stack in "real" recursion. Note: there might be such an algorithm, but I'm not aware of one. | |
| Nov 22, 2015 at 13:47 | answer | added | gnasher729 | timeline score: 1 | |
| Nov 22, 2015 at 13:23 | answer | added | hyde | timeline score: 32 | |
| Nov 22, 2015 at 13:16 | history | tweeted | twitter.com/StackProgrammer/status/668417740802269184 | ||
| Nov 22, 2015 at 12:58 | comment | added | hyde | A more interesting question would be, is there anything which can be done with help of LIFO (stack) of some kind, that can't be done with other kind of temporary storage (without simulating LIFO access). | |
| Nov 22, 2015 at 10:53 | answer | added | Alexander Kogtenkov | timeline score: 8 | |
| Nov 22, 2015 at 9:42 | answer | added | Ben1980 | timeline score: -6 | |
| Nov 22, 2015 at 6:51 | comment | added | 5gon12eder | Seeing the diverging directions into which the answers go (and having just failed myself at providing a better one) you might do anyone trying to answer a favor if you provide a bit more background and what kind of answer you are after. Do you want a theoretical proof for hypothetical machines (with unlimited storage and run-time)? Or practical examples? (Where “would be ridiculously complicated” might qualify as “can't be done”.) Or something different? | |
| Nov 22, 2015 at 6:00 | answer | added | Scant Roger | timeline score: 167 | |
| Nov 22, 2015 at 5:11 | answer | added | user40980 | timeline score: 79 | |
| Nov 22, 2015 at 5:06 | comment | added | Lightness Races in Orbit | I seriously doubt it. Recursion is a glorified loop. | |
| Nov 22, 2015 at 4:54 | review | First posts | |||
| Nov 22, 2015 at 5:27 | |||||
| Nov 22, 2015 at 4:45 | history | asked | Pikamander2 | CC BY-SA 3.0 |