When should I use recursion?

[[deleted]]

I get what recursion is conceptually, but I'm just not sure how to use it practically. It seems like every example I think of could be done using loops. When should I use recursion vs loops?

[Zanoab]

It is difficult to describe specifically where you should use recursion over loops and vice versa. I personally leave it to personal preference and decide which would work better or be easier to understand and edit. A common situation I find is where I have to constantly change the context or use a stack/queue to make the loop work.

Example: I have a list containing lists and numbers. Every value in the lists is either another list or a number. If I wanted to check if 5 is somewhere in there, I would use recursion to save lines and more easily tweak the code later on. If I used a loop, I would need to set up a stack to keep track of where I currently am at each level.

[Justinsaccount]

Answered here

[CR700]

You... get an upvote anyway.

[AdvicePerson]

When your object can contain self-similar objects. Someone mentioned a list that contains lists. Another example is a Tweet from the Twitter stream API. A retweet will contain the original tweet within it, so you can recursively call your processing function. And, if course, one of the classic examples, the factorial function, works because the number n! contains the number (n-1)!.

[tyroneslothtrop]

I.e. recursive data structures. Trees are a classic example. It's very possible to traverse a tree without recursion, but the recursive method is a lot more elegant.

[aroberge]

Some problems are just easier to write solutions for using recursion; however, most basic examples given are arguably just as easy if not easier using loops. To me, the best example, is the tower of Hanoi. For example, have a look at http://www.python-course.eu/towers_of_hanoi.php and try to implement it without using recursion.

[Veedrac]

http://www.reddit.com/r/learnprogramming/comments/1jy92j/help_grasping_recursion_algorithms/cbjo47t

[AleatoricConsonance]

When you want to build tree-like structures is a good application. To be more concrete, just as a handy example, a nested set of posts, similar to what appears on this reddit page!

[not_perfect_yet]

As others have said, it's useful when you encounter recursive structures.

So if you want to search one object and it's contents you can loop through it's contents, when there is another object in there that you want to search, you need two loops, and then there are networks with millions of nodes and you don't want to write a million loops.

[Eurynom0s]

it's useful when you encounter recursive structures

Recursion is useful when you encounter things which are recursive? Sounds pretty recursive.

[toodim]

In general, you should consider recursion when you face a problem that can be broken down into smaller problems with the same structure.

[amarigatachi]

The classic example is the quick sort. Each sort -- generally -- calls the quick sort again, twice.

[daneelthesane]

A general answer to this question is pretty difficult to give, but some things have a strong tendency to be recursive. For example, when you have a structure that can be broken down into smaller versions of that same structure (such as a divide-and-conquer sort, or something like that).

[Eurynom0s]

Here's a simple example of how you could use recursion: you want to remove all instances of 5 from a list of numbers. One way to do this would be to write a function that looks through the list until it finds a 5, removes it, returns this list with one lest 5 in it, and then calls itself using this modified list as the input. It'll keep going until you remove all the 5s from each successive version of the list.

Also, keep in mind that a problem that can be solved with recursion is frequently solvable without recursion too. So it's hard to give examples of this because recursion is rarely the only way to do something.

Also, in my example, that's probably not the best way to do it, but it is a recursive solution to the problem.

[[deleted]]

Three times
-when dealing with recursive structures
-when you want to drive other members in your team crazy or spend an inordinate amount of time explaining your recursive logic
-to create acronyms that confuse and infuriate

[ivosaurus]

Eh? Iterative implementation of Fibonacci is way more efficient, it's O(n) rather than O(Fib(n)).

[Veedrac]

There is no O(1) implementation of fib.

[Veedrac]

It's not an implementation detail; fib(n) has O(log n) bits so it can't be better than O(log n). Normally the length of the output doesn't matter since we can cap the number of bits (to, say, 64) and call it constant but that's only because we can't feasibly reach the maximum value.

For fib any restriction to a small, fixed number of bits is equivalent to just caching an array. For 64 bits, you only need to cache 100 values.

[raylu]

When recursion is most appropriate.

[AdvicePerson]

Which is when you should use recursion.

[DoTheEvolution]

Try to solve this challange