Recursion done inside of a variable

Question

I am a bit confused on how the compiler does recursion if it is in a variable. The only way to easily explain the question is if I show an example.

def recur_var(s1, s2):
    '''Test for recursion in variables.'''
    if s1 == '':
        return s2
    elif s2 == '':
        return s1
    else:
        test = recur_var(s1[:-1], s2[:-1])
        if s1[-1] == '1' and s2[-1] == '1':
            return True 
        return test

The only recursion done in the above code is inside the variable that is above in priority over everything else, besides base cases.

I realize this code is all over the place in terms of what it does, but my question is, in the trace of this stack, does test only ever become the leftovers of the slicing?

Does test do the recursion all the way down to the base cases without ever checking if s1[-1] and s2[-1] are both 1? In other words, does it 100% ignore everything beneath it when it calls, or does it ignore itself and follow the rest of the code, then call?

I realize this was probably asked and worded awfully, but I'm very confused myself so I don't know a better way.

Answer 1

If you put the line:

print("testing s1[-1] == '1' and s2[-1] == '1' with s1, s2 = " + s1 + ", " + s2)

right after the recursive call and right before if s1[-1] == '1' and s2[-1] == '1':, typical output is:

>>> recur_var('1001','1100')
testing s1[-1] == '1' and s2[-1] == '1' with s1, s2 = 1, 1
testing s1[-1] == '1' and s2[-1] == '1' with s1, s2 = 10, 11
testing s1[-1] == '1' and s2[-1] == '1' with s1, s2 = 100, 110
testing s1[-1] == '1' and s2[-1] == '1' with s1, s2 = 1001, 1100

So you only get to testing the top-level s1, s2 (what you see in the final line) after the recursion has finished. In earlier stages of the recursion that test is run, but with smaller strings that are slices of the original string.

Answer 2

Every time you call recur_var you create new strings with …[:-1]. But they don't overwrite the s1/s2 variables already existing in the methods. So the check in the next line are actually done on the original values which got passed to the function call.

Basically every time you call this function it creates a new set of variables (so s1, s2 and test in your case). For example:

def foo(x):
    x = x - 1
    if x > 0:
        foo(x)
    print(x)

foo(3)

This will output 2 to 0 and each call will have its own x. And you can assign to them all you want and it won't do a thing to the variables in the other function calls.

For example it first calls foo(3) and then it reduces x by 1 and calls foo(x) which is foo(2) and in there it reduces x by 1 again, but x in the context of foo(3) is still 2.

Now the exceptions are global variables and if you modify a variable (doing x = 42 does not modify x but it overwrites x).

Answer 3

SHORT ANSWER

Yes, the function recurs on the shortened strings before it checks the end characters. It does that checking only after it exhausts one of the strings -- as it returns back down the call stack.

---

CAVEATS

1. The compiler generates machine code; the run-time system or Python interpreted actually does the recursion
2. There is no such thing as recursion inside a variable. A variable is data; recursion is a control flow concept. I'm not quite sure what you mean by your usage.

In addition, you haven't described what your routine is supposed to do. What it actually does is to find out whether a character '1' appears at the same distance from the end of the two given strings. If so, it returns True; otherwise, it returns the first (abs(len(s1) - len(s2)) characters of the longer string. This is very strange behaviour, returning two different data types.

---

TRACING YOUR EXECUTION

Learn some debugging techniques. They'll serve you well as you continue programming.

To work on your program, I did two things:

1. I converted this to structured programming: one exit for the routine. I put the desired result into a variable and only returned at the bottom of the routine. This allows me to trace execution at a single exit point.

This looks like:

def recur_var(s1, s2):
    global depth
    '''Test for recursion in variables.'''
    if s1 == '':
        result = s2
    elif s2 == '':
        result = s1
    else:
        test = recur_var(s1[:-1], s2[:-1])
        if s1[-1] == '1' and s2[-1] == '1':
            result = True 
        else:
            result = test

    return result

2. Next, I inserted debugging traces: print statements to follow the entry and return, and an indentation counter to make things easier to visualize.

This looks like:

depth = 0
def recur_var(s1, s2):
    global depth
    depth += 1
    print "  "* depth, "ENTER", "s1 =", s1, "s2 =", s2
    '''Test for recursion in variables.'''
    if s1 == '':
        print "  "* depth, "s1 is empty; return s2"
        result = s2
    elif s2 == '':
        print "  "* depth, "s2 is empty; return s1"
        result = s1
    else:
        test = recur_var(s1[:-1], s2[:-1])
        print "  "* depth, "both strings have chars; test=", test
        if s1[-1] == '1' and s2[-1] == '1':
            result = True 
        else:
            result = test

    print "  "* depth, "LEAVE", "result =", result
    depth -= 1
    return result

print recur_var("8610", "17")
print recur_var("X8610", "X17")
print recur_var("hello", "world !")

... and the output from these tests is ...

   ENTER s1 = 8610 s2 = 17
     ENTER s1 = 861 s2 = 1
       ENTER s1 = 86 s2 = 
       LEAVE result = 86
     LEAVE result = True
   LEAVE result = True
True
   ENTER s1 = X8610 s2 = X17
     ENTER s1 = X861 s2 = X1
       ENTER s1 = X86 s2 = X
         ENTER s1 = X8 s2 = 
         LEAVE result = X8
       LEAVE result = X8
     LEAVE result = True
   LEAVE result = True
True
   ENTER s1 = hello s2 = world !
     ENTER s1 = hell s2 = world 
       ENTER s1 = hel s2 = world
         ENTER s1 = he s2 = worl
           ENTER s1 = h s2 = wor
             ENTER s1 =  s2 = wo
             LEAVE result = wo
           LEAVE result = wo
         LEAVE result = wo
       LEAVE result = wo
     LEAVE result = wo
   LEAVE result = wo
wo

This should let you figure out everything you need to know.