Recursion

  1. Even so python's list.sort function does not contain any recursion because those built-in functions are optimized to death. Along with file traversal, any tree traversal algorithm makes sense to do recursively since you need to keep track of the parent in the stack anyway.

  2. 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.

  3. Python 3.11 is bringing huge optimizations to recursion it is said. Having better frame management on the stack to help with resource usage.

  4. Python's stack is limited, so you should also make sure your recursive function is not growing the stack too large. This is usually not a problem for traversing things like filesystem trees, but probably is a problem for functions that recursively calculate things. You can see the limit with sys.getrecursionlimit(). It's 3000 on my machine. Plus I played around with this in ipython, and that lowers the limit by about 16 (presumably because ipython is wrapping the function call 16 times).

  5. 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)

  6. even in other languages, there is the principle "premature optimization is the root of all evil" - design needs to be nailed down to a certain extent before software is written, because in a lot of situations that's hard to change afterwards, but the implementation should always be done an a straightfoward and readable way until and unless profiling has identified a performance problem, because people aren't always best placed to predict where a performance problem will be (especially with modern compilers)

  7. Indeed. Problems that involve processing a tree- or graph-like structure of arbitrary depth pretty much require recursive solutions by definition. You can hammer the code into a while loop if you have to, but the nature of the problem is ultimately recursive, so it's best to represent that in the code explicitly.

  8. 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.

  9. 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.

  10. 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.

  11. 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.

  12. 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.

  13. 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.

  14. 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.

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

  16. 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

  17. I feel like the 1 dimensional list is how schools teach it, and it leaves a bad taste in everyone's mouth.

  18. 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.

  19. 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.

  20. 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.

  21. 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.

  22. There is a reason introductory computer science courses traditionally force you to use recursion as a primary means of doing things. There are a lot of problems that are much better solved by using it. If someone is saying recursion is bad overall, I would suspect them of lacking experience or having a limited range.

  23. 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:

  24. Also, not all recursive solutions can be tail call optimized. Oh certain functions that meet specific requirements can. You have to be able to pass the full state of the function via variables. You also need to be able to return results immediately without any further processing.

  25. Many people in the comments say it's okay to do recursion in python in some cases. I don't agree. Python is really not made for recursion, like most high level languages by the way. Why is it bad? 1/ Because of the memory usage. In fact, every time it calls itself once again, it adds the function call along with some context data of the call to the call stack. So just for the example imagine you wanted to repeat some action 10 times, doing it in a recursive way (instead of iterative way) would temporarily store in your memory some kind of list (stack) of 10 elements, and once all of the calls were done it will unstack them one by one. 2/ For time complexity: many people in the comments have claimed that recursive functions take more time to execute because each time it will need to return sth, etc. Wrong argument. In terms of optimisations, O(3n) is the same than O(n). In other words, the speed you lose by doing recursive instead of iterative is negligible. Or maybe not: most of the time if per recursion you make only one call of the function it should be moreless optimised. BUT if at each recursion you make more than 2 recursive calls to your functions, things can get really funky. Example, the Fibonacci function. Done in an iterative way, you'd need approx 10 iterations to calculate fib(10). So it's time complexity should be O(n). But if you do it in a recursive way, the time complexity would be O(n2) and that is a huge gap. What happens? When you call fib(10), it will call fib(8) and fib(9) which will call fib(8) and fib(7) etc... As you can see here fib(8) was done twice already, and moreless the same will happen at every level of recursion. You can visualise the calls of your function thanks to a tree. If you count the leaves at the very bottom of your tree you should get around 100, which is 10 squared. 3/ As your friend claimed, 90% (technically even 100%)of time you can do it in iterative way. And NO it will NOT make your algorithm less readable. More difficult to think,Yes, more difficult to read, most of the time no, it adds maybe a couple of lines... 4/ Due to the call stack limit. You can do maximum 2000 recursive calls iirc. You can make that limit higher but most would advise that it's not a Great idea if you don't want to have memory issues. Meaning that your tree or whatever recursive algo will not be deeper than 2000 levels (if you try to do so it will just throw an error), and trust me it's not a lot at all! When you deal with massive databases for example you will most likely encounter more than 2000 levels to go through. So then why is recursion a thing if it should be avoided in python? Recursion is great, it was the source of many super efficient algorithms, such as fusion sorting, fast sorting and many more. The most important thing to remember about recursion though is that it's mostly a concept-level feature. In fact thinking recursively may lead to more ideas and more optimal ways to solve problems. It doesnt mean it should be implemented this way though!!! Usually when an algorithm is coded recursively it's not that hard to convert to iterative without too much hassle. It's just that you'd have never thought about the algorithm in the iterative way in the first place. Computer scientifically speaking, recursive concept is a gold mine. Such as devide and conquer algorithms, often thought recursively they offer such a boost of speed. Now if you want to do and code recursive, for sure! But preferably not on python. You can check a list online of languages that support decent recursivity. Ocaml is a good example.

  26. You're using a problem that is badly suited for recursion. To be fair, you're not the only one. Every course I see seems to think that the Fibonacci sequence is a good recursive function. In fact, most examples school gave me we're just functions that take in a counter. It led me to believe recursion was pointless.

  27. 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.

  28. 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).

  29. 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.

  30. And you are right... Recursion are complex and should be avoided. One of the last refactor I've made was dropping a recursive method I've made that create multipart email.

  31. 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.

  32. Recursion is a beautiful solution for a mathematical problem. However for computer science, it is not always the most optimal solution. It depends on the depth of the recursion because it will need stack frames ( read memory ) for every recursion.

  33. 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.

  34. 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.

  35. 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.

  36. 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.

  37. 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.

  38. 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.

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

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

  41. 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.

  42. 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).

  43. 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.

  44. 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.

  45. 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.

  46. 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.

  47. 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.

  48. 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.

  49. 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.

  50. 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.

  51. Iterate is the key word here. You should never use recursion to iterate. Use it for things like Tower of Hanoi.

Leave a Reply

Your email address will not be published. Required fields are marked *

Author: admin