recursion depth error in python when dealing with lambda functions

Question

For context, let me first define some stuff. For a given natural number n, let theta and eta be two positive vectors of length n and epsilon be a vector of -1 and 1s of length n as well.

I am trying to implement an algorithm that computes the finite sequence of real functions g=(g_1,...g_n) with g_n=0 which verifies the following recurrence relation :

g_(i-1)(x)=f_i(x) if x*epsilon_i > x_star * epsilon_i and 0 otherwise,

with f_i(x)=2eta_i*(x-theta_i)+g_i(x) and x_star the zero of f_i (I am saying "the zero" because f_i should be an increasing continuous piecewise affine function).

Below is my attempt. In the following code, computing_zero is an auxiliary function that allows me to compute x_star, the zero of f, assuming I know its breakpoints.

def computing_g(theta,epsilon,eta):
    n=len(theta)
    g=[lambda x:0,lambda x:2*eta[n-1]*max(0,x-theta[n-1])] # initialization of g : g=[g_n,g_(n-1)]
    breakpoints_of_f=[theta[n-1]]
    for i in range(1,n):       
        f= lambda x:2*eta[n-1-i]*(x-theta[n-1-i])+g[i](x)
        x_star=computing_zero(breakpoints_of_f,f)
        breakpoints_of_f.append(x_star)
        g.append(lambda x: f(x) if epsilon[n-1-i]*x > epsilon[n-1-i]*x_star else 0)
    return(breakpoints_of_f,g)

Whenever i run the algorithm, i get the following error :

line 6, in <lambda>
    f= lambda x:2*eta[n-1-i]*(x-theta[n-1-i])+g[i](x)

  line 9, in <lambda>
    g.append(lambda x: f(x) if epsilon[n-1-i]*x > epsilon[n-1-i]*x_star else 0)

RecursionError: maximum recursion depth exceeded in comparison

I suppose there is some sort of infinite loop somewhere, but I am unable to identify where.

Your code would be a lot clearer if you replaced all the lambda expressions by normal function definitions, and it would make it easier to troubleshoot, more importantly. — joanis
– joanis, Commented Jun 12, 2022 at 1:21
I suspect part of the problem is that i is not saved in that definition of f, and i gets its final value even when you're trying to call an earlier instance of f. The value of i is not getting curried into the definition of f, just the symbol, and that symbol gets evaluation when you actually calls f. — joanis
– joanis, Commented Jun 12, 2022 at 1:49
@joanis - I think you're definitely on the right track here. I ran the following to verify (formatting as best as comments allow): g = [], for i in range(5):, f = lambda: i, g.append(lambda: f()), for pos in range(len(g)):, print(g[pos]()), and the output was "4" * 5 If I modify i before the second loop, then that's the value that will be displayed. — nigh_anxiety
– nigh_anxiety, Commented Jun 12, 2022 at 4:08
I think the solution is to define f using a Closure instead of a lambda function, so that the value of i can be set at the time the function is created instead of being a free symbol. The lookups from theta and eta would be handled at that time as well. — nigh_anxiety
– nigh_anxiety, Commented Jun 12, 2022 at 4:15
Exactly @nigh_anxiety, a closure is what's needed here, thanks for reminding me what that's called! Skywear, you'll find many hits if you Google "closure in Python", among them this one: medium.com/python-features/…. — joanis
– joanis, Commented Jun 12, 2022 at 15:38

nigh_anxiety · Accepted Answer · 2022-06-13 15:55:05Z

I took a stab at writing this with closures, but I can't verify if the results of the math are what you expected, as you didn't provide code for the function calculating zero, so I just made something up. I'm pretty sure that this should avoid the recursion issue you're seeing. Another change I made, is instead of using [n-1-i] for all of the indexes in the loop, I changed the loop to start at 2, and then every index check is just [-i]. The exception is when looking up the function in list g to use in calculating generating function f. There the index is now [i-1] instead of [i].

def get_func_f(eta, theta, i, g):
    """Generate function f(x)"""
    eta_i = eta[-i]
    theta_i = theta[-i]
    g_i = g[i-1]  # This is the one index working from left to right, and i will always be len(g)+1
    def f(x):
        return 2 * eta_i * (x - theta_i) + g_i(x)
    return f


def get_func_g(f, epsilon_i, x_star):
    """generate function g(x)"""
    def g(x):
        if epsilon_i * x > epsilon_i * x_star:
            return f(x)
        else:
            return 0
    return g


def computing_g(theta,epsilon,eta):
    n=len(theta)
    g=[lambda x:0,lambda x:2*eta[-1]*max(0,x-theta[-1])] # initialization of g : g=[g_n,g_(n-1)]
    breakpoints_of_f=[theta[-1]]
    for i in range(2,n):   # Start at 2 and just use [-i] instead of [n-1-i] everywhere.
        f = get_func_f(eta, theta, i, g)
        x_star=computing_zero(breakpoints_of_f,f)
        breakpoints_of_f.append(x_star)
        g.append(get_func_g(f, epsilon[-i], x_star))
        #print(f"{breakpoints_of_f=}\n{g}")
    return(breakpoints_of_f,g)


def computing_zero(a, b):
    """Completely made up as example code wasn't provided."""
    return -(a[-1]+b(a[-1]))

answer = computing_g(theta=[0.5,0.3,0.2,0.1],epsilon=[1,-1,1,-1],eta=[1,3,2,4])
print(f"breakpoints: {answer[0]}\ng={answer[1]}")

Output:

breakpoints: [0.1, 0.30000000000000004, -0.3000000000000004]
g=[<function computing_g.<locals>.<lambda> at 0x0000023F329CB670>, <function computing_g.<locals>.<lambda> at 0x0000023F329CB700>, <function get_func_g.<locals>.g at 0x0000023F329CB820>, <function get_func_g.<locals>.g at 0x0000023F329CB940>]

Collectives™ on Stack Overflow

recursion depth error in python when dealing with lambda functions

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related