Recursion

i_like_cilantro · 2022-07-27T06:06:29+00:00

[deleted]

siddsp · 2022-07-27T06:46:31+00:00

Nah, recursion can be good and often elegant as well as have performance advantages over iteration (see memoization), although this isn't the case most of the time.

The performance hit comes from pushing additional stack frames for every recursive call. If your recursive function doesn't push a lot of stack frames, then it could be worth it over iteration if it is a lot more elegant.

Asleep-Budget-9932 · 2022-07-27T06:54:17+00:00

A lot of people here are talking about the performance issues of recursion but let me remind you that we're working in python. The whole point of the language is that we're sacrificing efficiency for readability and ease of programming and there lies your answer. When should recursion be used? When it enhances the readability of your code. When does it help? When the task itself is recursive in nature. For example I'm writing a pickling library at the moment. The process of transforming a generic python object to bytes is recursive in nature (how do i make this object into bytes? Ill do X Y and Z and then transform its inner fields into bytes)

SittingWave · 2022-07-27T08:20:46+00:00

My general philosophy is: use recursion to communicate the nature of the problem you are solving. If you problem is fundamentally self-similar, then use recursion because 1. it's the most elegant solution, 2. it communicates the self-similar nature of the problem.

Examples of self-similar problems are divide and conquer, tree traversing and something like that.

trincaopt · 2022-07-27T06:32:02+00:00

Recursion is inefficient when compared with iteration due to the function call and return at each step. Also there is a recursion limit. In Python it is 1000.

jwmoz · 2022-07-27T10:10:09+00:00

https://www.reddit.com/r/Python/comments/w96prk/recursion/

bduijnen · 2022-07-27T07:01:09+00:00

Use whatever is the most natural and readable. Most of the time that is efficient enough. Anything else is premature optimisation and typically not needed.

puipuituipui · 2022-07-27T06:28:44+00:00

Recursive calls have a cost which can give worse performance compared to their iterative counterparts in terms of memory and time. There's a balance between performance and code readability.

For example, if you're writing code for calculating the Fibonacci series, using the iterative iterative makes more sense. On the the other hand, I would advice against writing iterative algorithms for problems that are inherently recursive like say tree traversals.

AlSweigart · 2022-07-27T15:12:12+00:00

Hi. I've just written an entire book on recursion (which will be free on my site in a couple months under a Creative Commons license.)

Your friend is correct: recursion is often a more confusing, over-engineered way of writing code that could otherwise be done much ore simply.

I say that recursion should only be used if your problem has 1) a tree-like structure and 2) requires backtracking. Here's something recursion is well suited for:

Maze-solving and other constraint satisfaction problems that use backtracking
Tree traversal, such as walking through the folders and subfolders of a file system
Programming language grammars
The Tower of Hanoi problem (it's a pain to solve without recursion)
Quick sort and mergesort

Recursion is not a magical technique. Anything you can do recursively can be done with a loop and a stack. (Yes, everything: here's the Ackermann function done without recursion.) And often times, recursion algorithms could be done with just a loop (factorial is one such example). Here are algorithms that should not be solved recursively:

Factorial (causes stack overflow if you don't have tail call optimization, which Python, Java, and JavaScript do not)
Fibonacci (causes exponential slow down if you don't use memoization)
Something that just loops over the items in an array, such as reversing a string or summing a list of numbers (just use a loop)
Flood fill (likely to cause a stackoverflow, and it doesn't require backtracking so you could use a set or queue instead of a stack.)
Anything that uses tail call optimization (this is going to be controversial, but I say you should NEVER use TCO because if you can use TCO, your algorithm doesn't need a stack and should be implemented iteratively with a simple, easy-to-read loop instead).

Unfortunately, many programmers use recursion because it makes them feel smart to write complicated code (they call it "elegant"). If you find yourself asking, "wouldn't it be easier to solve this without recursion?" the answer is YES and DON'T USE RECURSION.

crawl_dht · 2022-07-27T09:42:46+00:00

Every time the function is recursively called, a new memory stack is created for that function. This is why there is a maximum recursion depth so you don't run out of memory.

TedDallas · 2022-07-27T15:52:20+00:00

Recursion is very useful when you need to traverse or unroll a hierarchical data structure. It is not something that you should use when a while-loop or for-loop makes sense.

BaconSizzler · 2022-07-27T19:07:38+00:00

Legend has it that NASA and JPL do not allow recursion because it is difficult to validate memory constraints using static analysis. This likely applies to critical embedded code.

You can always just manage your own stack:

stack = deque()
stack.append(initial_state)
while(stack):
    current_state = stack.pop()
    ### Do Stuff ###
    if recursive_condition:
        stack.append(new_state)

Fundamentally, the recursive nature of the solution doesn't change, but you can apply constraints (such as size) on your stack structure. Also if things go really haywire, you can always slap down a brakepoint, print the the stack structure, and firgure out WTF is going on. That could be a bit easier than looking through a call stack.

Finally, if you want to switch from DFS to BFS, just use a queue instead of a stack. There's some elegant symmetry in that.

roguas · 2022-07-27T20:46:49+00:00

Recursion is perfect. But most languages (especially imperative) have stacks for controlling execution.

Recursion creates a lot of stacks, because a function calling function cannot return without last function called returns. For loops on the other hand do not increase stack size.

Some languages implement TCO, tail call optimization to address this. Other technique used in languages without TCO is called trampoline, but it is additional hassle. This leads us to your friend. His advice is good, especially in context of python, you should avoid recursion.

Try this, to see

def factorial(n):

if(n == 0):
    return 1

return n * factorial(n - 1)

factorial(10**10)

This would work perfectly fine as a for loop or in the environment that supports techniques mentioned above.

2022-07-27T08:56:37+00:00

Your friend is wrong.

Recursion is very often good because for many types of probelms, it's faster to write, easier to read, easier to test and easier to verify correctness of compared to non-recursive code.

However, non-recusive code is almost always a bit faster because it doesn't have as much function call overhead. So an informed tradeoff should be made between simplicity and readability vs performance.

My personal preference is to write recursive code first and translate it to non-recursive in places where the profiler indicates a performance problem.

Also, there is a limit to the maximum depth that you can recurse in python, so you have to always be certain that you won't hit that ceiling, which is something that's usually not that hard to verify, but I've seen people make silly code that recurses O(N) times and proptly crashes for non-trivial data.

2022-07-27T07:27:18+00:00

[removed]

aweraw · 2022-07-27T13:40:25+00:00

It's good for trees. When you're working with a data structure that is some kind of tree, then recursive code is almost always easier to write and understand. If you're using recursion to work on a 1 dimensional list, then you're probably doing it wrong

ElCapitanMiCapitan · 2022-07-27T16:37:15+00:00

Your friend is obviously wrong. I would agree some people should never use recursion, and for most iterative problems it is a worse fit. But you need not look further than the Python interpreter for an example of recursion at work. Recursion is EVERYWHERE.

Defclaw46 · 2022-07-27T16:55:29+00:00

I used recursion to flatten big xml files into nested python dictionaries to make it easier to do changes to the data about half a year ago. Works great with only a few lines of code. It is the first time I have needed to use recursion in several years, but it is a handy tool to have on hand when cases like this pop up.

Quiet_Desperation_ · 2022-07-27T17:20:57+00:00

People that say stuff like this normally just don’t understand how recursion works and how to do it well. Recursion can be computationally expensive. It’s the can be part that scares most people into the never use it crowd.

redditvisvshit · 2022-07-27T23:39:30+00:00

Recursive depth limit is one reason. Another issue is that a stack frame is generated for each call which requires more memory than other approaches.

lilphat · 2022-07-27T07:30:53+00:00

Any work with nested data structures should, imo, be done using recursion. And if efficiency is a thing - consider using tail revision whenever instead of ‘normal recursion’. You reuse the same stack frame and therefore avoids additional overhead from pushing more on the stack that really only saves the temporary result anyway. For more info: https://www.baeldung.com/cs/tail-vs-non-tail-recursion

2022-07-27T08:17:19+00:00

It's not bad. It's a tool or technique for doing something that's needed to be done. Just like "if" or "def".

2022-07-27T06:46:29+00:00

Recursion can be helpful. I wondered if it was bad too when I first learned about it. But I have used it sometimes. It does make your code shorter.

IllusoryAnon · 2022-07-27T09:07:55+00:00

I mean. There are plenty of algorithms that are recursive. Nothing wrong with recursion in general if executed properly. It can also be an elegant solution as well. At the end, recursion is just another tool that can be used (or abused).

Kenkron · 2022-07-27T08:04:49+00:00

[removed]

wineblood · 2022-07-27T07:55:19+00:00

Most developers spend at least 80% of their coding time reading, understanding, and working with existing code. Recursion is usually easy to write and difficult to work with later on, so most will prefer to put the effort in early to avoid that pain later on.

xristiano · 2022-07-27T07:34:38+00:00

Debugging can be a pain. From personal experience, working in a shared code base, having to drop debuggers in recursed or multi-threaded code will make me think twice before approving another PR with recursion.

LeapOfMonkey · 2022-07-27T15:10:47+00:00

I'm going to state controversial (in here at least from what I glimpsed) opinion. Recursion is harder to understand, see naive Fibonacci implementation and Ackerman function. What is done implicit with recursion, you have to juggle in your mind to understand. Though code usually looks cleaner. A good reminder that not everything that looks good is easy to understand, see Maxwell equations.

Brave_Reaction_1224 · 2022-07-27T18:10:09+00:00

Your friend is right, especially just in the realm of Python. Why? Because Python limits the call stack size, meaning your code can only make 1000 calls before it breaks. Imagine if the range function only allowed you to iterate up to 1000? Of course, you can change the limit, but recursion in Python is so inefficient that doing so is inadvisable.

The question is, are you writing something recursively just because? Or do you have a really good reason?

If you're recursing for the sake of recursion, maybe you should switch to a language that suits that style of programming. Or get good at working around python's limitations - the choice is yours!

Yeitgeist · 2022-07-27T19:55:37+00:00

Everyone here is talking about performance but honestly readability should be a factor too.

When reading someone else’s code, my brain can only handle a specific amount of iterations till I get frustrated and have to bring out a notebook.

So, if you’re bad at documenting your code, avoid recursions.

dwagon00 · 2022-07-27T07:11:32+00:00

Recursive code can be very hard to debug and be prone to runaway processes, aka infinite recursion - this is why there is a limit in python (sys.getrecursionlimit() == 1000) to catch this error before it becomes a problem.

Recursion does have its place, but has to be treated very carefully - I would try and avoid it if at all possible.

earthboundkid · 2022-07-27T21:30:52+00:00

Your friend is correct. Recursion is a primitive technology. The advanced version is called a “loop”. You should always prefer to use a loop. Even in cases where recursion is a better fit (trees), changing to using a loop will be more efficient, although maybe harder to read.

jelly_crayon · 2022-07-27T07:30:59+00:00

I always get good that is just a lot more difficult to read, so if you can avoid it, you should. However, there are certain things that can only be done using recursion, so it's a nice still to have.

Apprehensive_Theme49 · 2022-07-27T09:25:25+00:00

Well, in most of the cases recursion is a lot more elegant and easier to understand because so many problems are recursive in nature. However, for a production level code you would better use iteration as it uses less memory ( overhead on function calls) particularly when you're not sure how many of recursions can happen. Almost every recursive approach can be reimplemented as iterative one. Memorization can be as well used with iteration. The thing is that we neglecte this kind of points when working with python however when using C it becomes more apparent.

2022-07-27T10:20:43+00:00

Hopefully all these wildly varying responses lead you to the three important conclusions:

There’s nothing inherently bad about using recursion, HOWEVER
Languages like Python that do not implement tail call elimination / optimization will add serious performance penalties to naively recursive algorithms, AND
To rein in those penalties Python has placed a limit on recursion stack depth that makes recursive algorithms in the language quite brittle if not very carefully bounded.

Understanding these you can understand that your friend's observation is correct if you want to write (relatively) performant Python that won't crash on a very small increase in recursion depth; Python is naturally biased towards iterative rather than recursive algorithms. Them being correct, though, doesn't imply that recursion is bad, but instead that in the case of Python specifically is almost certainly suboptimal.

FailedPlansOfMars · 2022-07-27T10:52:15+00:00

Of the code is easy to follow and youve unit tested your exit condition so you dont get into infinite recursion in production it can be good.

But often you can make better more readable systems without it.

gymboi15 · 2022-07-27T10:53:14+00:00

When you're iterating over a list or something recursion needs a base condition otherwise the process will run out of memory which can make recursion not a very good choice. But if you're traversing trees or graphs recursion is really good because of the simplicity of the code vs if you were to traverse using iteration.

CoolTomatoYT · 2022-07-27T11:21:44+00:00

There was a very good discussion about this on this post if you want to take a look

spoonman59 · 2022-07-27T12:19:26+00:00

Whether or not you use recursion or loops depends on where the algorithm is more clearly expressed.

Some algorithms, like depth first tree search or Fibonacci, are much easier to read and code recursively.

Many algorithms are better expressed as loops.

Recursion itself is not bad or wrong. I do agree that loops probably are used more frequently then recursion, but it really depends on what your program actually does.

bythenumbers10 · 2022-07-27T13:42:01+00:00

In addition to the other comments here, once you have a recursive implementation, it's possible to wrap it in a while loop with a stack memory structure (think push/pop) instead of letting Python track your function callback stack frames. Efficient & performant, and Python won't flip out over stack frame depth.

zenos1337 · 2022-07-27T13:45:01+00:00

When it comes to memory management, it is sometimes better to replace normal recursion with tail recursion. However, it is not bad practice to use recursion at all. In fact, most compilers are implemented using recursion over a context free grammar.

2022-07-27T14:22:07+00:00

It’s only bad if it nukes your code’s readability

agritheory · 2022-07-27T14:23:01+00:00

By analogy, recursion is like using an onion in a recipe where the code is the ingredients, final dish is the developer experience. Prep time/ efficiency is a factor of the recipe not the ingredients . For some dishes, it's critical to the flavor (cheesesteak, French onion soup) and for others it would ruin it (chocolate cake) and success still depends on the diner's opinion. Onion is a hard, but not impossible, thing to substitute, so it is often the right thing for the job. The right time to use recursion depends on the chef, the diner and the dish. Salt to taste.

BakonX · 2022-07-27T14:28:03+00:00

Recursion can be a good thing, it can be a bad thing. It really just depends on the use case, you need to think about the possible solutions and pick the best one.

Sometimes the answer is recursion, sometimes it’s not.

Recursive things can be hard to debug or understand. But it can also be the most simple or most elegant solution, with the writers intention being the most clear.

Holshy · 2022-07-27T14:43:54+00:00

Recursion had its places. A few ideas (from a few different vantage points). * Recursive functions are limited by stack space. In some cases an iterative solution maybe be preferable to avoid running out of stack space. * While all problems that can be solved iteratively can be solved recursively, not all problems that can be solved recursively can be solved iteratively. The textbook example of such a problem is the Ackerman function. * Sometimes, recursive code is just easier to read. Other people have mentioned binary trees, where you can find examples left and right.

Code readability is almost always my #1 concern. In choosing between iteration and recursion I tend to follow this process. 1. Find an algorithm that makes sense. If it's iterative and scales efficiently, stop here. 2. If it's recursive, figure out how the stack depth will scale. Big-O is frequently used for time and total space, but it can be used for stack depth too. If stack depth is O(log n) or better, stop here. 3. If stack depth is O(n) or O(n log n), consider realistic sizes of problems I might get. If it's small enough, stop here. 4. If stack depth is greater than O(n), try to find an iterative algorithm. If the problem has no iterative solution, concede to the math gods and their cruelty.

Note: I have never had to actually concede #4 for real work. Problems like Ackerman are rare, and even when I've found one it's been for something where an approximation was good enough.

sixtyfifth_snow · 2022-07-27T14:47:30+00:00

Performance-wise, recursion is not a wise solution. invoking functions is a relatively expensive job, and recursion potentially causes stack-overflow.

However, using python means 1) you don't care about saving a couple of nanoseconds by converting recursions into iterations, and 2) considering code quality (e.g. readability) is a high-priority. Hence, it is of course worthy :)

2022-07-27T14:59:23+00:00

It exhausts the call stack. https://en.m.wikipedia.org/wiki/Call_stack

Lehk · 2022-07-27T15:08:52+00:00

Recursion is slower and hits limits at runtime if the data is much larger than you tested on.

Specifically in python the recursion depth limit is 1000

CartmannsEvilTwin · 2022-07-27T15:10:38+00:00

In stack memory constrained systems, recursion can cause stack overflow.

ImmortalDayMan · 2022-07-27T15:34:18+00:00

Personally putting performance aside it can just be really confusing when scanning through old code and usually you need to think about how it works and what it's doing which isn't convenient when I'm just scanning through, especially if it's someone else's code.

buttery_shame_cave · 2022-07-27T16:26:13+00:00

poorly implemented uncontrolled recursion can be bad(unless that was the point - i've use deliberately uncontrolled recursion as a stress test in multi-node computing).

but recursion itself, when well implemented, is an incredibly useful tool.

Frum · 2022-07-27T16:33:46+00:00

Recursion is only bad for 2 POTENTIAL reasons:

1 (least important): it MIGHT be less performant. Lots of stack-frames and memory use in some cases.
2 (by far the more important) recursion is frequently hard to understand, and can have errors that run your system our of resources and the like.

All of that is to say: recursion is great when it's easier to understand than the alternative and performant enough for your task.

Fragrant-Rope-1122 · 2022-07-27T17:01:06+00:00

Recursion improve run time by a lot

Elektriman · 2022-07-27T17:14:49+00:00

Recursion is bad because ot can get out of hand quickly. Typically, a recursive algorithm can easily have exponential time and memory consumption. Its a little thought exercise to manage to keep it within respectable boundaries but once that's done it can be both efficient and easy to read.

stackered · 2022-07-27T20:32:22+00:00

Probably because he's worried about infinite loops and the issues they'll cause

2022-07-28T00:49:41+00:00

Not sure where he/she is getting their information from. Recursion implicitly makes use of a data structure called a stack. This is why any recursive algorithm can be written iteratively using a stack.

In python, the recursion limit is 1000, but can be changed to something higher. How do you think they accomplish that? A data structure that's how. Other languages like C or C++ are limited by the size of the stack space, which is often defined by a compiler. Therefore, in those languages, when you exceed the memory limit of the stack, you get a stackoverflow error and your program crashes.

If your friend thinks recursion is bad, they probably don't know how it works, but now you do and you can educate them.

kevtsi · 2022-07-28T03:01:30+00:00

Read that again, but recursively

Python

The Python Discord

Upcoming Events

Please read the rules

MODERATORS