Is it advisable to write recursive functions in Python

Question

I have written a verilog (logic gates and their connectivity description basically) simulator in python as a part of an experiment.

I faced an issue with the stack limit so I did some reading and found that Python does not have a "tail call optimization" feature (i.e. removing stack entries dynamically as recursion proceeds)

I mainly have two questions in this regard:

1) If I bump up the stack limit to sys.setrecursionlimit(15000) does it impact performance in terms of time (memory -- I do not care)?

2) Is there any way I can circumvent this limitation assuming that I can live without a stack-trace.
I ask this because Verilog mainly deals with state-machines which can be implemented in an elegant way using recursive functions.

Also, if I may add, in case of recursive function calls, if there is a bug, I rely more on the input which is causing this bug rather than the stack trace.

I am new to Python, so maybe experts might argue that the Python stack trace is quite useful to debug recursive function calls...if that is the case, I would be more than happy to learn how to do that.

Lastly, is it advisable to write recursive functions in Python or should I be moving to other languages?

If there any work-around such that I can continue using python for recursive functions, I would like to know if there any performance impact (I can do profiling though).

Answer 1

2) Is there any way I can circumvent this limitation assuming that I can live without a stack-trace. I ask this because Verilog mainly deals with state-machines which can be implemented in an elegant way using recursive functions.

There is a way to avoid tail calls without changing your existing logic too much, simply rewrite your tail calls to return a thunk and use a trampoline to call that thunk. If you need to pass in complex state between transition, you can use continuation passing style to pass them around. This style of writing code is very well suited for writing a state machine.

An example is perhaps clearer, suppose that you start with this recursive implementation of a fizzbuzz state machine that uses tail calls to pass control to the next transition:

def start():
    return increment(0)

def fizz(n):
    print 'fizz'
    return increment(n)

def buzz(n):
    print 'buzz'
    return increment(n)

def fizzbuzz(n):
    print 'fizzbuzz'
    return increment(n)

def increment(n):
    n = n + 1
    if n > 100:
        return terminate()
    elif n % 3 == 0 and n % 5 == 0: 
        return fizzbuzz(n)
    elif n % 3 == 0: 
        return fizz(n)
    elif n % 5 == 0:
        return buzz(n)
    else:
        print n
        return increment(n)

def terminate():
    raise StopIteration

try:
    start()
except StopIteration:
    pass

To avoid the tail calls, you simply wrap all the tail calls in lambda (or alternatively, functools.partial) and add a trampoline:

def start():
    return lambda: increment(0)

def fizz(n):
    print 'fizz'
    return lambda: increment(n)

def buzz(n):
    print 'buzz'
    return lambda: increment(n)

def fizzbuzz(n):
    print 'fizzbuzz'
    return lambda: increment(n)

def increment(n):
    n = n + 1
    if n > 2000:
        # strictly speaking, transitions that takes no arguments
        # like terminate don't need to be wrapped in lambda
        # this is added here only for symmetry with others
        return lambda: terminate()
    elif n % 3 == 0 and n % 5 == 0: 
        return lambda: fizzbuzz(n)
    elif n % 3 == 0: 
        return lambda: fizz(n)
    elif n % 5 == 0:
        return lambda: buzz(n)
    else:
        print n
        return lambda: increment(n)

def terminate():
    raise StopIteration

def trampoline(func): 
    try:
        while True:
            func = func()
    except StopIteration:
        pass

trampoline(lambda: start())

Now you can have lots more fizzbuzz without hitting the recursion limit.

Answer 2

A lot depends on the specific nature of the recursive solution you're trying to implement. Let me give a concrete example. Suppose you want the sum of all values in a list. You can set the recursion up by adding the first value to the sum of the remainder of the list - the recursion should be obvious. However, the recursive subproblem is only 1 smaller than the original problem, so the recursive stack will grow to be as big as the number of items in the list. For large lists this will be a problem. An alternate recursion is to note that the sum of all values is the sum of the first half of the list plus the sum of the second half of the list. Again, the recursion should be obvious and the terminating condition is when you get down to sublists of length 1. However, for this version the stack will only grow as log₂ of the size of the list, and you can handle immense lists without stack problems. Not all problems can be factored into subproblems which are half the size, but when you can this is a good way to avoid stack overflow situations.

If your recursive solution is a tail recursion, you can easily be converted into a loop rather than a recursive call.

Another possibility if you don't have tail recursion is to implement things with a loop and explicitly store your intermediate state on an explicit stack.