If something COULD be done with recursion, should it?

The amount that you practically use recursion will be very small when you begin developing and much larger as you gain experience. In general, recursion and iteration are interchangeable, and mechanically so; that is, you don't actually need to understand the algorithm at play to convert it from one to the other, you only need to understand loop invariants and exit conditions. Recursion can feel like an 'overcomplicated' way to solve it problem, but as you get more comfortable with it, it actually makes solving problems significantly easier. This is because instead of writing functions that process large data structures, which can be difficult to hold in your head, your functions will operate on very very small data structures and compose to work on larger ones (among other reasons). I wouldn't go out of my way to use recursion when iteration suffices and is simple enough, but I would certainly practice with recursion and identify when it is a good tool for problems. Being comfortable with it will certainly help you as you advance in your career, and at some point it will be necessary to at least understand it well enough to troubleshoot because you can guarantee that you will encounter it in the wild.

Fibonacci is a great example because it can be succinctly expressed via recursion... yet the naive recursive solution is very slow.

Fibonacci is a classic example of recursion with overlapping subproblems. Consider fib(5). To compute that, you need fib(4) and fib(3). But to compute fib(4), you need fib(3) and fib(2). if you're not careful, you'll compute fib(3) twice. And that compounds. Each fib(3) will want to compute fib(2) and fib(1).

Dynamic programming is the general solution to this kind of problem. In dynamic programming, you compute each subproblem just once and then store the result.

Your iterative Fibonnaci is essentially an optimized version of the dynamic programming solution. In DP, you'd store every value you had previously calculated. But it's clear that Fib only needs the two most recent values. Your iterative implementation takes advantage of that property.

Recursion is a key concept in programming. Recursion is a good idea to use when the algorithms are easier to read and write using a recursive method. One good use case for recursion is when you have an indeterminate depth problem. As an example of this, let's look at recursive CTEs. Say you want a query that pulls the name of all employees and their managers. So you pull the name of Al and his manager Bill. Bill is also an employee, and he has a manager name Carl. So you want to do the same thing for Bill. And Carl is also an employee, and he has a manager named Dan. So you want to do the same for him, etc. These problems are way easier to solve using recursion. Go ahead and try implementing something like a binary tree without using recursion. Even if you can do it, that doesn't mean it won't be super difficult to understand, debug, or maintain. Meanwhile, the recursive algorithm, if it's well written, won't be any of these. If you're not in a situation where you're in a good use case for recursion, you should 100% use iteration.

Recursion introduces a marginal performance overhead (this answer puts it simply enough) and also the possibility of a stack overflow when dealing with large data sets.

However, it's often the simpler and more intuitive way to express a solution (in my opinion). For instance when dealing with recursive data structures. In addition, some languages feature tail call optimization which eliminates the aforementioned call stack issues.

How will I "know" when to use recursion instead of iteration?

When there is no reasonable iterative solution, or the iterative solution is much more complicated or less readable. Anything that uses a 'tree' data structure, for example a file system, lends itself to recursion - it's easy to recursively do something to all files in all subdirectories for example.

Resource-wise, is recursion faster / lighter than iteration? What are some arguments for / against its use?

No, generally compilers can't optimise recursion as easily as loops - it's likely to perform worse than a comparable iterative solution. Your Fibonacci solution will beat the pants off a naive recursive solution that isn't memoized (isn't storing previously calculated values in a dictionary for lookup).

Loops and recursive calls are equivalent, you can write any loop as a recursion, and you can write any recursion as a loop.

So, no, you absolutely shouldn't write a recursion whenever you can. Format to be true, it would also have to be true that you should never use a loop.

Specifically, anyone who writes the Fibonacci generator recursively is completely and utterly incompetent. If they have any excuse, it is that their teachers have been equally useless.

Writing it as a loop is easy and straight forward. You can see what happens immediately and you don't need to balance multiple levels of iteration in your head.

When people tell you that code should be written for other programmers, that you should readability and ease of understanding in mind - this is what they are talking about.

If you are using simple recursion of the type f(x) { If (x<2) return 1; return f(x-1)+f(x-2) } you're multiplying the work that you do - unless your compiler is clever enough to collapse the function into a loop:

f(10) = f(9) + f(8) -> f(9) = f(8) + f(7) f(8) = f(7) + f(6) -> f(8) = f(7) + f(6) f(7) = f(6) + f(5) f(7) = f(6) + f(5) f(6) = f(5) + f(4) -> ...

And for each step, you need to remember all the previous steps to boot.

It's insane. Don't ever do it.

Of course that doesn't mean you should never use recursion. With the Fibonacci sequence - or it's abomination of a sibling the factorial - It's easy to avoid: You start calculating at the easy end, where you know what's happening and what the results will be.

So, unsurprisingly, recursion tends to be a good option when you don't know what the other end looks like unless you work your way there.

Look for a file in a directory tree. You don't know how many sub dirs or files you have in any given spot, or where they are. You will have to branch out into arbitrarily many new directions. Recursion to the rescue.

Explore a maze. Same thing. Make sure you remember positions you've already explored..

You only know the options of the next step when you've reached the previous step. And you only know which of those options to use if you've explored them all the way down.

In the maze, should you turn left or right? You can only tell if you know which leads you to the exit.

And anyone that teaches recursion with unsuitable examples creates new programmers that use fancy constructs or paradigms just for the sake of using them, not because they are a good choice for the given situation

If you're trying to get a solution with the shortest possible code for whatever reason, recursion might be an option - it should tell you something that that's essentially an intentional abandonment of best practices.

Recursion should typically be done when there's a base case and the problem can be solved by applying a function continuously over its own output.

Personally, I use recursion when the problem can be expressed, and more easily interpreted, in a recursive rather than iterative form. Such as the fibbonnachi, factorial, or folder/file manipulation.

Recursion is usually more resource intensive for non-functional programming languages. The space complexity is typically the same, or greater, than an interactive counterpart. As each call to the function will add a new function to the stack frame. Time complexity is typically the same though each operation can be more costly as a new function is added to the stack.

I like how this one question created such a ripple effect on other people. Recursion is inevitable in functional programming, as many of the languages lack loops but allow for tail recursion (long story short means recursion but the call stack remains constant). In OOP languages and the like I only see recursion useful when working with graphs. Like traversing them feels much easier when using recursion or when needing some backtracking algorithms.

Some tasks are just far easier to do with recursion, if something is easier to follow (logically) using one method or another then use that method.

An example of something that is easier with recursion is traversing a directory, basically recall the method for each sun directory and perform whatever task you want with each file. This can be done with iteration, it's just more complicated.

The Fibonacci sequence is the classic example of recursion but as you noticed it is trivial to do in a loop so doesn't demonstrate the full power of recursion.

One specific advantage of recursion is that a stack of previous elements is retained that you do not have to manually manage. Useful for for example traversing data structures with forward pointers but not backward ones. Like for example a tree without parent pointers.

Data structures with pointers in both directions are inherently unsafe in terms of memory management (they allow dangling pointers) - which is the reason they wouldn't compile in Rust, a language that ensures memory safety at compile time.

Thus recursion may allow memory-safe data structures - recursive data structures - that still have a simple and intuitive implementation.

(And no, even though that might sound awesome that doesn't mean "always".)

Pros of using recursion:

1. Some problems that have a recursive mathematical definition are simpler to solve using recursion.

2. Easier to keep track of state calculation order (useful in problems such as flattening a tree).

3. It is more efficient in problems where it is possible to skip calculating some states (pruning in AI or dynamic programming).

Cons of using recursion:

1. Most problems are simpler to solve without using recursion.

2. There are time and memory overheads to consider (read about stack memory vs heap memory).

Does java have tail-call optimization, these days? If not, recursive implementations will be limited by feasible stack depth. So, I would say steer clear of recursion as long as you're using java, unless and until it gets TCO.

[removed]

M2c: in 99% of all cases where you can use recursion it is still super annoying to read and counter-intuitive to use. Recursion has to have a really strong advantage for the specific code block to be a choice.

Recursion is a bad idea in languages that don't allow for the tail call optimization because it can lead to stack overflows. Having a loop that will just self destruct for large iteration counts is Too Silly.

It is useful for analysis I think because it separates a proof out into handling the base case and handling the recursive case. But I'm not a computer scientist.

In terms of clarity... I dunno. We see so many loops while programming and so little recursive code. So I guess whatever inherent advantage recursive code has regarding clarity, the familiarity of loops might win out.

Your mileage may vary, offer not valid in functional programming languages.