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?
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
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.
@mehrdad-pedramfar posted an excellent answer. Also you can try this more elaborate one:
def my_recursion(current_value, first_portion):
if current_value == 5:
return
print(current_value)
if current_value == 0 or not first_portion:
my_recursion(current_value + 1, False)
elif first_portion:
my_recursion(current_value - 1, True)
my_recursion(4, True)
Basically the same as the first. The output is differ - you'll get double 0. Just to show you can print before and after recursive call.
def bounce(n):
if n >= 0:
print(n)
bounce(n - 1)
print(n)
3 2 1 0 0 1 2 3
