Interesting. Why is recursion bad? After all, this is the same cycle, even more so, with the ability to transfer parameters. Such a "loop" can be stopped by return . And it happens that without it in any way (Fibonacci numbers).
Why in real projects avoid its use?
None of the means of language can be bad or good by definition.
Recursion allows a programmer to express his thoughts more clearly to everyone (and first of all to the compiler), but the price for this is an understanding of what is happening. You need to understand what a stack is, how it works, what is put on the stack when you call it. You need to have a slightly more developed imagination in order to understand when the recursion stops and what will happen to it during calls. You need to understand why global variables need to be changed carefully and, at the same time, why there should be as few variables as possible in the function (up to reuse).
However, any recursive algorithm can be written without recursion. (Usually using a dynamically expanding array)
The main problems specifically recursion - the inability to use it. Many programmers, looking at the code from https://ru.stackoverflow.com/a/39232/182935, will say that it is correct. In fact - there is a gross error hidden - an exponential rather than a linear increase in the number of operations and memory (well, if you write not on a functional PL).
Also from the classic recursion - the inability to properly set the stack using compilation keys (how often in Java you collected from the command line, for example, or maybe you remember how to start a thread with a large stack).
Therefore, a resume (sorry for being rude), if you ask this question, then do not use recursion, if you realize what you are doing - then this is a very handy tool that improves the readability of the code in a number of tasks and allows the compiler to work and not you in the sense of optimizations.
экспоненциальный а не линейный рост - why linear? Fibonacci is perfectly calculated for O(log(n)) - vp_arthRecursion is not bad. It just requires careful attention to the stack. As it grows with each step, which often leads to overflow.
And in principle, it can be replaced by an iteration (loop). What is usually advised to do in languages where there is no tail recursion .
For example, in scala, you can explicitly indicate that the tail recursion should be used with the @tailrec annotation, then the call will be replaced with a transition (go to).
Incorrect use of recursion can lead to stack overflow and huge computational overhead. However, the recursive approach has a significant advantage in the naturalness of the algorithm: when using the apparatus of mathematical induction, you can easily test the correctness of the result (bearing in mind the features of data representation in memory). I recommend to mark recursive procedures with the @tailrec annotation to check the optimization of the function.
To optimize the recursive method, they usually resort to tail recursion: an additional parameter is passed to the function that stores the results of the previous calculation. However, in some cases this is not enough: for example, in the same example with Fibonacci numbers: here you need to store a list of results. For this you can use lazy collections, inside or outside the method. Sometimes there are more complex tasks when, for example, you need to find the best list of results. In this case, you can use recursion with clipping elements.
Resource cost. While the program goes deep into recursion, memory space is allocated for local variables. And in the loop, the variables are simply updated.
NotSouchOfMemoryException - FlippySource: https://ru.stackoverflow.com/questions/620933/
All Articles