![]() So yes, it's a larger number, but it's not anything that's going to alter what algorithms and data structures you can and can't use. In a real world scenario the effective figure would be less. This represents a best case scenario, because the function is called directly from main and there are hardly any local variables to be found anywhere. On my system (MinGW gcc 4.8.1) it dies at a depth of about 65k. Here is a testcase in C that models the recursive in-order traversal of a pathologically unbalanced tree (via a cycle.) It prints out the depth so that you can see how far it got when it faults. Stack frames in C are much more lightweight than in Python, which makes the threat of blowing the stack much less likelyĪs I said, it's probably on the order of up to tens of thousands. And by all means, use the standard library before writing anything yourself. You can see several examples of what that looks like on this page. Now on to your actual question: if you're going to use recursion get rid of that temporary storage and turn the function into a generator. If anyone knows the source of this "don't use recursion in Python" stuff, I'd like to hear it. Python's strong suit is writing clear and concise code, and that is something that recursion can really excel at, when used properly. There's no arguing with that, but on the other hand Python's strongest suit has never been performance, so it's an odd thing to bring up here. Many languages do not have tail call elimination that doesn't mean that recursion is out of the question.įunction call overhead is relatively high. Again, that means you can't pretend you're using Haskell or Lisp, but that shouldn't be news. Python does not have tail call elimination. Moreover, a few thousand frames (up to perhaps several tens of thousand) is approximately the maximum recursion depth that you're going to get language like C or C++, based on the typical default stack size of around 2MB - 4MB, so it's not like Python's limit is so much smaller than other languages, and I don't hear anyone saying that C is unsuitable for recursion. That's also not what I would call reasonable for a non-functional language. Similarly, Python is not Lisp and you should not try to traverse linked lists using recursion. ![]() But that's not what I consider a reasonable algorithm, because unbalanced trees are so pernicious. If you have an unbalanced binary tree, then in the worst case it's going to degrade to a linked list, and traversing it recursively could easily blow out the stack. That's why I say that 1000 frames is more than enough for any reasonable algorithm. The number of permutations of a sequence of length 1000 is 1000!, a number with 2568 decimal digits. When finding permutations, the recursion depth required is the length of the sequence, since you recurse once every time you remove an element. That's a number with 302 decimal digits, which is several hundred orders of magnitude larger than the number of atoms in the observable universe. A balanced binary tree of depth 1000 will h1 nodes. It should be more than enough for any reasonable algorithm.įor example, the recursion depth necessary to traverse a tree is simply the depth of the tree. Perhaps people think that's not a very high number. Its purpose is to prevent exhausting the system stack, such that you get a nice Python error instead of an ugly segmentation fault when you make a mistake and blow out the stack. ![]() It is adjustable, and typically defaults to 1000. Python has a built-in limit on recursion depth. I can think of a few reasons why it persists: I don't know where this meme comes from, and I wish it would die. That's flat out untrue, and there absolutely no reason to avoid recursion in Python.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |