function that contains a function of itself?

Question

The title is a little weird, but I don't know exactly how this is called, so plz forgive me with the abstract title....

I've found a code like this online:

def lcs(xstr, ystr):
    """
    >>> lcs('thisisatest', 'testing123testing')
    'tsitest'
    """
    if not xstr or not ystr:
        return ""
    x, xs, y, ys = xstr[0], xstr[1:], ystr[0], ystr[1:]
    if x == y:
        return x + lcs(xs, ys)
    else:
        return max(lcs(xstr, ys), lcs(xs, ystr), key=len)

I am new to python, and I don't understand how you can call lcs(xs, ys) in

return x + lcs(xs, ys)

To my understanding, lcs() is not yet fully defined, and I'm confused how you can call a function of itself inside itself....

Also, I don't know what key = len is doing in

max(lcs(xstr, ys), lcs(xs, ystr), key=len)

I know how max( 1st, 2nd ) works, but I don't know what the third parameter is doing. What does "key" mean, and why is "len" used as a value of "key"?

Answer 1

This is called recursion. The body of the function isn't evaluated at all until you call it. Think of lcs in the body as just a name; when you call the function, Python will apply the same lookup rules it applies to any name to see what it refers to; typically* it refers to the same function.

---

*Typically, because you can break a recursive function by playing some games with the names.

def foo():
    print("hi")
    foo()

g = foo
def foo():
    print("new function")

If you call g(), it will output

hi
new function

instead of print an infinite stream of lines containing hi. (Well, almost infinite; eventually you'll get a RuntimeError because Python caps the size of the call stack.)