Is there any way to perform this type of recursion in C++ or python?

Let us say I have a function called my_func(a,b,s,t). Suppose, I want a and b to be passed by value, but I want s and t to be passed by reference. As in, I want to some how pass in let us say (4,5,s',t'). The function performs computations by calling my_func(a/2,b/2,s/2,t/2). The thing is, there is a base case at the “bottom” of the recursion that gives concrete values to s and t.

Let me give a mini example:

def e_euclid(a,b,s,t):
if (a == b):
    s = 4
    t = -3
    return a

if (a%2 == 0 and b%2 == 0):
    if (s%2 == 0 and t%2 == 0):
        return 2*e_euclid(a/2,b/2,s/2,t/2)
        return 2*e_euclid(a/2,b/2,(s+b)/2,(t-a)/2)

So, I would call this function as e_euclid(a,b, something, something) but then I would have to supply concrete values for s and t. Can you guys kind of see what I’m trying to do here?

Doing recursion where I return (s,t) would lead to a tough computation that I don’t wish to perform, so I would like to do it this way.


Your code seems broken, already that base case (?) with a == b and s = 4 and t = -3 doesn’t make sense. But see this C++ implementation and my Python translation using single-element lists instead of C++’s references:

def gcd(a, b, x=[None], y=[None]):
    if b == 0:
        x[0] = 1
        y[0] = 0
        return a
    x1, y1 = [None], [None]
    d = gcd(b, a % b, x1, y1)
    x[0] = y1[0]
    y[0] = x1[0] - y1[0] * (a // b)
    return d

a, b = 123, 321
x, y = [None], [None]
print(gcd(a, b, x, y), x, y, a*x[0] + b*y[0])

Output (Try it online!):

3 [47] [-18] 3

I think you’re trying to use the binary version of the algorithm, that should be doable the same way.