Additionally, most C++ implementations use a special feature called tail recursion elimination (see later in this post) and optimize some recursive code into iterative equivalents. And being a fully compiled language, loops (including recursion) are much faster in C++ than in Python (the reason why special Python modules like numpy/scipy directly use C routines). Let me first answer your direct questions:īecause C++ has no limitation on recursive call depth, except the size of the stack. (Nearly) everything is cheaper in C++, except the translation from source code to an executable program. Why are recursive calls so much cheaper in C++?Ĭ++ is a compiled language. Hence, the exception doesn't generally apply to C++ either.ĭisclaimer: The following is my hypothesis I don't actually know their rationale: The Python limit is probably a feature that detects potentially infinite recursions, preventing likely unsafe stack overflow crashes and substituting a more controlled RecursionError. While C++ compilers can perform the elimination as an optimization, it isn't guaranteed, and is typically not optimized in debug builds. Python is not such a language, and the function in question isn't tail-recursive. ² Exceptions to this rule of thumb are certain functional languages that guarantee tail-recursion elimination - such as Haskell - where that rule can be relaxed in case of recursions that are guaranteed to be eliminated. I wouldn't typically recommend touching that limit due to portability concerns. This too is configurable on some systems. The default size differs between systems, and different function calls consume different amounts of memory, so the limit isn't specified as a number of calls but in bytes instead. ¹ The underlying limitation is the execution stack size. This is C++-specific since Python doesn't have the concept of automatic storage. Other recursions may be converted to iteration using external data structures (usually, a dynamic stack).Ī related rule of thumb is that you shouldn't have large objects with automatic storage. Tail-recursive functions are trivial to re-write as iterations. Logarithmically growing recursion is typically fine. In general: You should not write² algorithms that have recursion depth growth with linear complexity or worse. This limitation also applies to all function calls, not just recursive ones. This underlying limitation¹ applies to both C++ and Python. However, too deep a function chain will result in a stack overflow. That limit is configurable as shown in Quentin Coumes' answer. The issue is that Python has an internal limit on number of recursive function calls. So generally, this will require a lot of hard work on the part of the programmer. However, this will swap the initial and the terminal conditions, and the latter is tricky for many problems (e.g. For Fibonacci numbers, this is easy to do. Of course, one solution is to replace recursion with iteration. Why are recursive calls so much cheaper in C++? Can we somehow modify the Python compiler to make it more receptive to recursion? Then Python too will give the right answer.įor n=50000 C++ finds the answer 151 within milliseconds while Python crashes (at least on my machine). We are taking modulos to keep the output size reasonable and using pairs to avoid exponential branching.įor n=5000, the C++ code outputs 783, but Python will complain RecursionError: maximum recursion depth exceeded in comparison Return ((x+x) % 997, (x+2*x) % 997)īoth will find the answer 996 without issues. Suppose we want to compute some Fibonacci numbers, modulo 997.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |