Help grasping recursion algorithms

Whether recursion is easier really depends. It also depends on the language, but I'm going to stick with Python for now.

I'll try not to bore you with silly recursive mathematics like fibonacci and factorial. Those are trivial and infrequent.

I've also assumed a fair bit more knowledge than I should've; if you're stuck on any of what I've said just ask. The point isn't the code per se, though.

Say you were travelling around a filesystem and listing all the files. If you were to define this iteratively you'd find quite a few problems.

WARNING: This is not good code. Use os.walk. This is purely example material. Also there are infinite loops in here.

directory = "/home"
for item in os.listdir(directory):
    qualified_item = os.path.join(directory, item)

    if os.path.isdir(qualified_item):
        # Placeholder: Need to change directory

    else:
        print(qualified_item)

For the placeholder, you might be tempted to do:

        directory = qualified_item
        print("entering", qualified_item)

but you need to remember to start the loop again, so put everything in a "while":

import os

directory = "/home"

while True:
    for item in os.listdir(directory):
        qualified_item = os.path.join(directory, item)

        try:
            if os.path.isdir(qualified_item):
                directory = qualified_item
                print("entering", qualified_item)
                break

            else:
                print(qualified_item)

        except FileNotFoundError:
            pass

Also you need to break out of a directory once you've finished it. Now we have to store a list of what directories we've been in:

import os

directories = ["/home"]

while True:
    for item in os.listdir(directories[-1]):
        qualified_item = os.path.join(directories[-1], item)

        try:
            if os.path.isidir(qualified_item):
                directories.append(qualified_item)
                print("entering", qualified_item)
                break

            else:
                print(qualified_item)

        except FileNotFoundError:
            pass

    else:
        print("leaving", directories.pop())

But.. ah! You need to store what position in the loop you're in because you reset from the top each time when you go back up the loop:

import os

directories = [("/home", iter(os.listdir("/home")))] # Hacky hack hack

while True:
    directory, contents = directories[-1]

    for item in contents: # "contents" remembers its position
        qualified_item = os.path.join(directory, item)

        try:
            if os.path.isdir(qualified_item):
                directories.append((qualified_item, iter(os.listdir(qualified_item))))
                print("entering", qualified_item)
                break

            else:
                print(qualified_item)

        except FileNotFoundError:
            pass

    else:
        print("leaving", directories.pop()[0])
        if not directories: break

See how problematic this is? Now try adding proper fallback to that ;P.

Let's do it recursively:

import os

def list_files(directory):
    for item in os.listdir(directory):
        qualified_item = os.path.join(directory, item)

        try:
            if os.path.isdir(qualified_item):
                list_files(qualified_item)

            else:
                print(qualified_item)

        except FileNotFoundError:
            pass

list_files("/home")

That's it. State is handled for free. That is the true advantage of recursive algorithms.

This happens in many cases -- you want to go down a path and return to the original state.

Finally, it's worth noting that Python programs aren't traditionally recursive. The majority of my code is non-recursive, it's only when it's easier to express recursively that I go back to recursion. That is fine. If you only like imperative stuff it won't hurt too badly while you're learning.

>>> def very_recursive():
...     very_recursive()
... 
>>> very_recursive()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in very_recursive
  File "<stdin>", line 2, in very_recursive
  File "<stdin>", line 2, in very_recursive
  File "<stdin>", line 2, in very_recursive
  ... lots more ...
  File "<stdin>", line 2, in very_recursive
  File "<stdin>", line 2, in very_recursive
  File "<stdin>", line 2, in very_recursive
  File "<stdin>", line 2, in very_recursive
RuntimeError: maximum recursion depth exceeded

def add1(lst, place=0):
    if len(lst) == place: return
    lst[place] += 1
    add(lst, place+1)