198

Recursion is not intrinsically better or worse than loops - each has advantages and disadvantages, and those even depend on the programming language (and implementation). Technically, iterative loops fit typical computer systems better at the hardware level: at the machine code level, a loop is just a test and a conditional jump, whereas recursion (...


167

Yes and no. Ultimately, there's nothing recursion can compute that looping can't, but looping takes a lot more plumbing. Therefore, the one thing recursion can do that loops can't is make some tasks super easy. Take walking a tree. Walking a tree with recursion is stupid-easy. It's the most natural thing in the world. Walking a tree with loops is a lot less ...


140

As explained by Brian Goetz (Java Language Architect at Oracle) in this video: in jdk classes [...] there are a number of security sensitive methods that rely on counting stack frames between jdk library code and calling code to figure out who's calling them. Anything that changed the number of frames on the stack would break this and would cause an ...


119

Loops are very much not recursion. In fact, they are the prime example of the opposite mechanism: iteration. The point of recursion is that one element of processing calls another instance of itself. The loop control machinery merely jumps back to the point where it started. Jumping around in code and calling another block of code are different operations. ...


41

You misunderstood recursion: although it can be used to replace iteration, there is absolutely no requirement for the recursive function not to have iterations internal to itself. The only requirement for a function to be considered recursive is the existence of a code path through which it calls itself, directly or indirectly. All correct recursive ...


38

This depends on your point of view. If you look at computability theory, then iteration and recursion are equally expressive. What this means is that you can write a function that computes something, and it doesn't matter whether you do it recursively or iteratively, you will be able to choose both approaches. There is nothing you can compute recursively ...


37

Yes, they do, but not only because they can, but because they have to. The key concept here is purity: a pure function is a function with no side effects and no state. Functional programming languages generally embrace purity for many reasons, such as reasoning about code and avoiding non-obvious dependencies. Some languages, most notably Haskell, even go ...


37

It depends. Some problems are very amenable to recursive solutions e.g. quicksort Some languages don't really support recursion e.g. early FORTRANs Some languages assume recursion as a primary means for looping e.g. Haskell It's also worth noting that support for tail recursion makes tail recursive and iterative loops equivalent, that is, recursion doesn't ...


37

Saying that X is intrinsically Y only makes sense if you've got some (formal) system in mind that you are expressing X in. If you define the semantics of while in terms of the lambda calculus, you might mention recursion*; if you define it in terms of a register machine, you probably won't. In either case, people probably won't understand you if you call a ...


33

Actually you should break the function down first: A loop has a few parts: the header, and processing before the loop. May declare some new variables the condition, when to stop the loop. the actual loop body. It changes some of the header's variables and/or the parameters passed in. the tail; what happens after the loop and return result. Or to write it ...


31

Are there any cases where a task can only be done using recursion, rather than a loop? You can always turn recursive algorithm into a loop, which uses a Last-In-First-Out data structure (AKA stack) to store temporary state, because recursive call is exactly that, storing current state in a stack, proceeding with the algorithm, then later restoring the ...


30

The specific meaning of "recursive" in this context is "operating on a directory and its contents, including the contents of any subdirectories". The word "recursive" is used here, because at least conceptually, this is easily implemented by a recursive algorithm: procedure check_in_directory (d : directory) for each entry e in d <== ...


28

JavaScript does not perform tail recursion optimization, so if your recursion is too deep, you may get a call stack overflow. Iteration doesn't have such issues. If you think you are going to recurse too much, and you really need recursion (for example, to do flood-fill), replace the recursion with your own stack. Recursion performance is probably worse ...


28

I'm concerned about this because I am developping a project which involves a heavy use of recursive structures and recursive function calls. I don't want the application to fail when I start using it for more than just small tests. Unless your language environment supports tail call optimization (and your recursion is a tail call), a basic rule of thumb is: ...


28

This is possible but a really bad idea; work out the number of threads you will spawn when calculating fib(16), say, and then multiply that by the cost of a thread. Threads are insanely expensive; doing this for the task you describe is like hiring a different typist to type each character of a novel. That said, recursive algorithms are often good ...


26

There are a number of good ways of looking at this. The easiest thing for me is to think about the relation between "Inductive" and "Coinductive definitions" An inductive definition of a set goes like this. The set "Nat" is defined as the smallest set such that "Zero" is in Nat, and if n is in Nat "Succ n" is in Nat. Which corresponds to the following ...


23

Java doesn't have tail call optimization for the same reason most imperative languages don't have it. Imperative loops are the preferred style of the language, and the programmer can replace tail recursion with imperative loops. The complexity isn't worth it for a feature whose use is discouraged as a matter of style. This thing where programmers want to ...


20

Update: since ES2015, JavaScript has TCO, so part of the argument below doesn't stand anymore. Although Javascript doesn't have tail call optimization, recursion is often the best way to go. And sincerely, except in edge cases, you're not going to get call stack overflows. Performance is something to keep in mind, but premature optimization too. If you ...


20

It depends on how strictly you define "recursion". If we strictly require it to involve the call-stack (or whatever mechanism for maintaining program state is used), then we can always replace it with something that doesn't. Indeed, languages that lead naturally to heavy use of recursion tend to have compilers that make heavy use of tail-call optimisation, ...


19

A return statement passes a value back to the immediate caller of the current function's call-frame. In the case of recursion, this immediate caller can be another invocation of that same function. In most languages, if you don't use the return value of a function you called (recursively or not), either that return value gets discarded or it is a ...


19

If you advance one step and subtract two from the length, you get a new sublist with the ends removed. Observe that the code does not just subtract from the length. It starts the sublist at n.next. For example, start with the list abcde, with length 5. On the first iteration, you have the sublist of length 3 starting at the second position, or bcd. On ...


19

The guiding principles here should be separation of concerns: The caller should invoke a function only with the parameters that are relevant for the result regardless how the calculation is performed; The called function should provide the result as best suit the needs, whether it's iterative, recursive, cached or a combination of any of these. ...


18

You're comparing recursion vs iteration. Without tail-call elimination, iteration is indeed more efficient because there's no extra function call. Also, iteration can go on forever, whereas it is possible to run out of stack space from too many function calls. However, iteration requires changing a counter. That means there must be a mutable variable, which ...


18

The key here is stack frames. Lets take a look at your first example: public static int incrementI(int i) { if (i == 5){ return i; } else { incrementI(i + 1); } return i; } On the first call, you have a variable named i, with the value of 0. Since i isn't 5, its going to call incrementI again with 1. This ...


17

There's no universally agreed on definition of "better" when it comes to programming, but I'll take it to mean "easier to maintain/read". Recursion has more expressive power than iterative looping constructs: I say this because a while loop is equivalent to a tail recursive function and recursive functions need not be tail recursive. Powerful constructs are ...


17

By default, the CLR allocates 1 MB to the stack for each thread (see this article). So, it's however many calls it takes to exceed this amount. That will vary depending on how much space on the stack each call is using for things like parameters and local variables. You can even make it throw a StackOverflowException with a single call if you're willing ...


17

Keep in mind that the language implementation must support tail recursion optimization. I don't think the major java compilers do. Memoization means you remember the result of a calculation rather than recalculating it every time, like: collatz(i): if i in memoized: return memoized[i] if i == 1: memoized[i] = 1 else if odd(i): ...


Only top voted, non community-wiki answers of a minimum length are eligible