Python, Make an iterative function into a recursive function

Question

I've created an iterative function which outputs 4 3 2 1 0 1 2 3 4.

def bounce2(n):
    s = n
    for i in range(n):
        print(n)
        n = n-1

    if n <= 0:
        for i in range(s+1):
            print(-n)
            n = n-1
    return
bounce2(4)

If I want a recursive function that does the exact same thing, how should I think?

Answer 1

Try this:

def bounce(n):
    if n >= 0:
        print(n)
        bounce(n - 1)

        if n:
            print(n)

bounce(4)

the output will be: 4 3 2 1 0 1 2 3 4

Answer 2

Expected output:

4 3 2 1 0 1 2 3 4

Let me put it into a diagram:

4
  3
    2
      1
        0
      1
    2
  3
4

Let's put that into code:

def bounce(n):
    print(n)
    if n:
        bounce(n - 1)
        print(n)

Or I can see it as a tree traversal - down and up (well, the tree is pretty linear in this case):

↓
  4
↓ | ↑
  3
↓ | ↑
  2
↓ | ↑
  1
↓ | ↑
  0

There are multiple ways how to do a tree traversal, I would pick DFS here - depth-first search.

DFS pseudocode:

procedure DFS(G,v):
    label v as discovered
    for all edges from v to w in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G,w)

Actually it's designed for graphs, not just trees; for trees we don't have to do the "label as discovered" part.

Translate this DFS to Python:

def dfs(node):
    for child_node in node:
        dfs(child_node)

In the 4 3 2 1 0 case we don't need the for becase there is exactly one or zero child nodes - n - 1 as long as n > 0:

def our_dfs(n):
    if n > 0:
        child_node = n - 1
        our_dfs(child_node)

But that does just the traversal and nothing really useful yet. Let's inject our "business logic":

def bounce(n):
    # stuff that happens before we go down
    print(n)
    # descend
    if n > 0:
        child_node = n - 1
        bounce(child_node)
    # stuff that happens after we are back from processing the subtree
    if n > 0:
        print(n)

Because we believe in good craftsmanship and we want to produce clean code (OK I am starting to be joking now) we want functions that do only one thing - one function for DFS, one function that represents our tree, separate function(s) for our business logic:

def dfs(node, child_factory, before_stuff, after_stuff):
    before_stuff(node)
    for child_node in get_child_nodes(node):
        dfs(child_node, child_factory, before_stuff, after_stuff)
    after_stuff(node)

def get_child_nodes(n):
    if n:
        yield n - 1

def print_before(node):
    print(node)

def print_after(node):
    if node:
        print(node)

def bounce(n):
    dfs(n, get_child_nodes, print_before, print_after)

bounce(4)

Maybe we could make the dfs function a bit simpler by using nested function:

def dfs(node, child_factory, before_stuff, after_stuff):
    def f(node):
        before_stuff(node)
        for child_node in get_child_nodes(node):
            f(child_node)
        after_stuff(node)
    f(node)

Hey, lookign at it, I have one more idea... We could modify this to a function that returns a function (closure) that can do DFS:

def make_dfs(child_factory, before_stuff, after_stuff):
    def dfs(node):
        before_stuff(node)
        for child_node in get_child_nodes(node):
            dfs(child_node)
        after_stuff(node)
    return dfs

So the bounce program now becomes:

def get_child_nodes(n):
    if n:
        yield n - 1

def print_before(node):
    print(node)

def print_after(node):
    if node:
        print(node)

def make_dfs(child_factory, before_stuff, after_stuff):
    def dfs(node):
        before_stuff(node)
        for child_node in get_child_nodes(node):
            dfs(child_node)
        after_stuff(node)
    return dfs

bounce = make_dfs(get_child_nodes, print_before, print_after)

bounce(4)

So, what's so cool about this solution? (note: still joking, partially) You know, Python has a recursion limit. There is a finite number of how many function calls can be nested and this number is pretty low. That's a big downside (sometimes even security concern) of processing unknown inputs using recursive functions. So what now? Well, just replace the implementation of make_dfs with something stack-based (see that DFS Wikipedia page) instead of recursion. Done. You don't have to touch anything else.