CODEWITHSUNDEEP
pythonrecursionbig-ospace-complexity
Selnay
Selnay

Reputation: 711

Recursion applied to lists vs trees in Python

My main concern with recursion is the recursion limit in Python, which I think is 1000. Taking this into account, I want to discuss two scenarios:

Scenario 1: Applying recursion for a balanced tree (binary)

For example, to search the maximum value in a tree:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def max(root):
    max_left = max(root.left)
    max_right = max(root.right)
    if max_left > root.value and max_left > max_right:
        return max_left
    if max_right > root.value and max_right > max_left:
        return max_right
    else:
        return root.value

Here, the maximum number of calls in the stack at any given time will be the height of the tree, which is log_2(n) where n is the number of elements in the list. Given that the limit in Python is 1000 calls, the tree could store up to 2^1000 (or 2^999) elements without reaching the call limit. For me, that is not a real limitation so I assume we are OK using recursion here.

Scenario 2: Applying recursion for a list

A dummy example would be computing the max of a list, so that we return the max between the head of the list and the result of the same function over the rest of the list:

def max(l):
    if len(l) == 1:
        return l[0]
    max_tail = max(l[1:])
    if l[0] > max_tail:
        return l[0]
    else:
        return max_tail

Output:

>>> max(list(range(998)))
997
>>> max(list(range(999)))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in max
  File "<stdin>", line 4, in max
  File "<stdin>", line 4, in max
  [Previous line repeated 995 more times]
  File "<stdin>", line 2, in max
RecursionError: maximum recursion depth exceeded while calling a Python object

So my understanding is that for lists recursion is not a reasonable option, since it cannot generally process lists larger than 999 (or even less, depending on the stack trace).

Now, my questions:

  1. Is it reasonable to use recursion to process balanced trees?
  2. Is it true that for most problems it is just not an option (lists, non-balanced trees, etc)?
  3. Anything else that I should take into account here? I am just trying to learn more about when recursion is the good option in general when using Python.

Upvotes: 2

Views: 240

Answers (2)

ggorlen
ggorlen

Reputation: 56905

Firstly, bear in mind that a language is not the same as the implementation of a language. The call stack size in Python varies by implementation. The limit of 1000 applies to CPython but not necessarily all implementations.

Is it reasonable to use recursion to process balanced trees?

Recursion is reasonable for balanced trees. As you've described quite clearly, the maximum call stack depth is a logarithmic factor on the size of the structure. You'd need a huge input to blow the stack.

With a list or degenerate unbalanced tree, recursion is inappropriate because the maximum call stack depth is linear on the structure length.

That said, I don't find it necessary to use self-balancing trees often in Python. Most work is done on lists and dicts, occasionally nested and recursively defined. The fact that recursion happens to be a good fit for structures like trees doesn't imply that it's widely applicable in general in Python.

Is it true that for most problems it is just not an option (lists, non-balanced trees, etc)?

Yes, but recursion is inhibited by design in CPython. Python is not a functional language. CPython doesn't support tail call optimization and "never" will.

Guido has a great blog post that defends CPython's anti-recursion design. Regardless of whether you agree with this design or not, tools should generally be used as intended, not as one wishes them to be.

In a pinch, Python (as a multi-paradigm language) can support code written in a functional style and there are workarounds to make long recursion work, but that doesn't change the fact that they're workarounds.

Anything else that I should take into account here? I am just trying to learn more about when recursion is the good option in general when using Python.

Function calls in CPython have more overhead (time and space) than iteration, so there are performance issues to consider even when the structure size fits in the call stack or you use a trick to support deep recursion.

Using setrecursionlimit is unsafe and almost never necessary. Such an option is not available in most languages. Increasing it means you're running the risk of the operating system killing the CPython interpreter. Sure, fiddling with the limit can come in handy for quick scripts and debugging, but it's not a general solution.

The tag is flooded with questions from well-meaning CS students tasked with solving problems with recursion similar to your example that blows the stack using Python and other non-functional languages. The quantity of these posts and the confusion on the part of the students suggests that the CS education system has a role in pushing recursion as the default option for iteration. Recursion is only as elegant as the extent to which the language was designed for it. The fact that recursion tends to be confusing to students is more a symptom of the misapplication of it to imperative languages where recursion is a second-class citizen after loops than anything inherent in recursion itself.

You'll probably never need recursion in Python other than school assignments, algorithm coding challenges and the rare practical business application use. But if you have a hammer, everything looks like a nail, so this isn't to say you can't apply recursion to each and every problem you see, it's that you probably shouldn't.

Recursive thinking is very valuable, and this isn't an attack on recursion as a tool in general, just recognizing that Python is particularly ill-suited for using it (as are most other imperative languages).

Unrelated to recursion and I understand your code is just a demonstration, but max is a builtin function, so I'd pick a different name. Taken alone, max(list(range(999))) looks like it should work.

Upvotes: 3

Holp
Holp

Reputation: 294

You can do trampolining in Python if you truly wanted to write your code in a recursive manner. But writing your code iteratively is a lot more realistic.

You can create a trampoline function based on generators as illustrated in this blog post:

def tramp(gen, *args, **kwargs):
    g = gen(*args, **kwargs)
    while isinstance(g, types.GeneratorType):
        g=g.next()
    return g

Also you can change the recursion limit in Python, not always recommended, and could seldom be called a proper solution; but it is possible.

from sys import setrecursionlimit
setrecursionlimit(10**8)

Upvotes: 2

Related Questions