Python recursion evaluate only if necessary

user_7662085 0
Viewed 106

Say I have these two functions:

def s(x,y,z):
   if x <= 0:
       return y
   return z

def f(a,b):
    return s(b, a+1, f(a,b-1)+1)

If I were to try and find f(5,2) in my head, it would go like this:

f(5,2) = s(2,6,f(5,1)+1)
f(5,1) = s(1,6,f(5,0)+1)
f(5,0) = s(0,6,f(5,-1)+1) = 6
f(5,1) = 7
f(5,2) = 8

I never evaluate f(5,-1) because it is not needed. The s function is going to return 6, since argument x is zero, thus evaluation of argument z is unnecessary.

If I were however to try and run this in python, it would keep recursing forever or or until I get a maximum recursion depth error, presumably because python wants to evaluate all the arguments before executing the s function.

My question is, how would I go about implementing these functions, or any similar scenario, in such a way that the recursion stops when it is no longer needed? Would it be possible to delay the evaluation of each argument until it is used in the function?

python-3.x python
2 Answers

Your mind is working with 'insider knowledge' of how s() works. Python can't, so it can only follow the strict rules that all argument expressions to a call will have to be evaluated before the call can be made.

Python is a highly dynamic language, and at every step of execution, both s and f can be rebound to point to a different object. This means Python can't optimise recursion or inline function logic. It can't hoist the if x <= 0 test out of s() to avoid evaluating the value for z first.

If you as a programmer know the third expression needs to be avoided in certain circumstances, you need to make this optimisation yourself. Either merge the logic in s into f manually:

def f(a, b):
    if b <= 0:
        return a + 1
    return f(a, b - 1) + 1

or postpone evaluating of the third expression until s() has determined if it needs to be calculated at all, by passing in a callable and make s responsible for evaluating it:

def s(x, y, z):
   if x <= 0:
       return y
   return z()   # evaluate the value for z late

def f(a, b):
    # make the third argument a function so it is not evaluated until called
    return s(b, a+1, lambda: f(a, b - 1) + 1)
user_1002970

When a function is called, all arguments are fully evaluated before they're passed to the function. In other words, f(5,-1) is being executed before s is even started.

Fortunately there's an easy way to evaluate expressions on demand: functions. Instead of passing the result of f(a,b-1) to z, pass it a function that computes that result:

def s(x,y,z):
   if x <= 0:
       return y
   return z()  # z is a function now

def f(a,b):
    return s(b, a+1, lambda:f(a,b-1)+1)

print(f(5,2))  # output: 8
user_12229510
Related