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

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.