Back to back recursion

Déjà vu’

I first heard the term ‘recursive’ back in 2013. At first I thought: “I learned cursive back in grade school, what’s so hard about efficient writing?”

Recursive functions are functions which, for a lack of better understanding, call themselves to accomplish a task. I’ve been researching recursion and how it actually works on youtube. I’ve stumbled upon a rather informative video with an example I found to be worth discussing here.

def count(n):
if n > 0:
print n
count (n - 1)
else:
print "Done"

Specifically, an example studied was the example:

>>> count(3)
3
2
1
Done

In my Slog today I will be dissecting this rather simple example, which I find may help deepen my understanding of recursion for other more complex examples.

To begin, the function count treats its argument n as a local variable. In the second code block, we have passed in n = 3 which is then passed into the if statements. If this n — value is greater than 0, then the code will first print n (which is 3), then create a new call to the function count.

I like to think of this step as a stalagmite. When water drips from the ceiling to the bottom of the stalagmite, a new layer of salt is formed. Similarly, every time count is called recursively, I like to think of a new (temporary) ‘layer’ being formed which is calling the function with a slightly modified argument. In the example above, we know it to be n-1. So count is called now within this new ‘layer’ with an argument of 3–1 = 2. Now, within this layer, the argument 2 is again entered into the if statement. If 2 >0, then 2 is printed and yet another call to count is instantiated.

This process repeats for the second ‘layer’ of count(n-1), where the argument now refers to 2–1 = 1. 1 will be printed and the next line of code will then call on to pass an argument of 1–1 = 0. At this point, the fourth ‘layer’, the argument will hit the else block and promptly return “Done”. However, the final step is that all these ‘layers’ were only temporary as stated above. Each ‘layer’ is then out of code to write and its “activation frames” go away starting with the deepest layer. In this case we had layer 4 as the deepest, where n = 0.

With respect to the image of my journal posted above, I find that this function exemplifies beautifully the general outline of a recursive function. It has an if — else statement to stop the recursive process. There are multiple conditions within the function which enable it to complete a task — in this case to count backwards from the nth argument.

Recursion seems like a powerful tool to have in our toolkit. I am going to need far more practice with this, but I feel like the idea of recursion translates well between most object-oriented programming languages for my later years.

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.