Just had a midterm last week. One of the questions presents a useful opportunity to talk about recursion and what it's all about.
Recursion is more or less the programming equivalent of a fractal. Basically it's a function that calls on itself until it eventually(hopefully) converges on a base case. This is an especially useful technique when working with objects that refer to themselves. So before we look at a recursive function, let's look at a recursive data structure, Trees.
Trees are a class of objects with a node that contains a value. And like normal trees, Trees can branch out to other nodes that contain their own value. These branches are called children and they are a list of nodes i.e. Tree objects.
Beside is a pictorial representation of a Tree. In code, this Tree would be represented as:
If this looks like a nightmare to read, then rest assured, many feel the same way. Lists of objects within lists of objects within objects. All referring to the same data structure. Hence the need for recursion if we wish to manipulate Trees.
So let's say I wish to check if all the nodes in a Tree had the same given value.
I would build a recursive function like this:
Notice how I call the function check_all inside of the return statement itself? That's recursion.
Let's say, I want to check if all the nodes in a Tree have a value of 5. I would check if the value of the individual node of the Tree was indeed 5 using the highlighted code, then I would check the children to see if the value of the other nodes that branched off were 5.
How do I check the children? Well, I'd call on check_all again but this time applying it to each individual node in the list, and in doing so, I'm running the same highlighted code on each node. And once I've checked all the nodes that were branched off, then I can conclude if all the nodes possess the same given value of 5.
In this example, you can say the highlighted code was the base case where the function eventually converged on.
If it's not too clear yet, just let it sink in, maybe use a few examples and see how it goes. The best way to learn recursion is by trusting where the code goes and having a good sense of mathematical intuition.
It is therefore with great dismay that I admit to a lack of either qualities..... And yes, I know my code isn't completely correct. There is a special case where it fails. See if you can spot it.
Recursion is more or less the programming equivalent of a fractal. Basically it's a function that calls on itself until it eventually(hopefully) converges on a base case. This is an especially useful technique when working with objects that refer to themselves. So before we look at a recursive function, let's look at a recursive data structure, Trees.
class Tree: """Bare-bones Tree ADT""" def __init__(self: 'Tree',
value: object =None, children: list =None): """Create a node with value and any number of children""" self.value = value if not children: self.children = [] else: self.children = children[:] # quick-n-dirty copy of list def __repr__(self: 'Tree') -> str:
"""Return representation of Tree as a string"""
return ('Tree(' + repr(self.value) + ', ' + repr(self.children) + ')')
Trees are a class of objects with a node that contains a value. And like normal trees, Trees can branch out to other nodes that contain their own value. These branches are called children and they are a list of nodes i.e. Tree objects.
Beside is a pictorial representation of a Tree. In code, this Tree would be represented as:Tree(2, [Tree(7, [Tree(2), Tree(6, [Tree(5), Tree(11)])]), Tree(5, [Tree(9, [Tree(4)])])])
If this looks like a nightmare to read, then rest assured, many feel the same way. Lists of objects within lists of objects within objects. All referring to the same data structure. Hence the need for recursion if we wish to manipulate Trees.
So let's say I wish to check if all the nodes in a Tree had the same given value.
I would build a recursive function like this:
def check_all(t: 'Tree', value: object =None, c: int =0) -> bool: """ Returns True if and only if all nodes in Tree object have the same given value. If no value is given, then returns True if and only if all nodes in Tree object have the same value. """ return (True if (value is None and not c) else t.value == value) and all([check_all(x, t.value, 1) for x in t.children]) Notice how I call the function check_all inside of the return statement itself? That's recursion.
Let's say, I want to check if all the nodes in a Tree have a value of 5. I would check if the value of the individual node of the Tree was indeed 5 using the highlighted code, then I would check the children to see if the value of the other nodes that branched off were 5.
How do I check the children? Well, I'd call on check_all again but this time applying it to each individual node in the list, and in doing so, I'm running the same highlighted code on each node. And once I've checked all the nodes that were branched off, then I can conclude if all the nodes possess the same given value of 5.
In this example, you can say the highlighted code was the base case where the function eventually converged on.
If it's not too clear yet, just let it sink in, maybe use a few examples and see how it goes. The best way to learn recursion is by trusting where the code goes and having a good sense of mathematical intuition.
It is therefore with great dismay that I admit to a lack of either qualities..... And yes, I know my code isn't completely correct. There is a special case where it fails. See if you can spot it.
