This post is my attempt to summarize recursion. Bear in mind that my grasp on the concept is weak, having had only a few weeks to wrap my head around what is undoubtedly a complex and mind-bending concept. It requires, I think, a little bit of trust in the computer that it will be able to follow the logic behind the code even though you don't really know the specifics of how it does so.
Before I begin, I would like to state that my definitions and explanations may not be entirely correct, as their main purpose is to describe the phenomenon of recursion, not necessarily to provide accurate definitions and explanations. In other words, I intend to be more colloquial than I probably ought to be.
So as I see it, recursion is the phenomenon of calling a function within its own code in order to avoid repetitive code and allow for deeper functions that do not rely on repeated for loops or unnecessarily long code. An example of a useful instance of recursive code is when dealing with class Tree- a sueful structure for several reasons, and unfortuneately requiring quite a bit of recusion.
Recursive functions require a base case. That is to say, the simplest situation in which no recursion is necessary. Often, this base case will be implemented frequently, at the end of every recursive call, so be careful when choosing both its condition and its code. Recursion base case looks like the following:
def count_nodes(tree):
if tree.children == []:
return 1
The code under the else clause will be the recusrive code. What we've learned so far is that there should be another function that is used to keep track of the information gathered in all the recursion calls. So in this example, if we are attempting to count the number of nodes in a tree, the else clause would look like the following:
else:
return 1 + sum([count_nodes(x) for x in tree.children])
What will happen here is that if the node that we've entered had no children, the function would return 1 for 1 node, the parent node. Otherwise, it returns 1 and then goes through each child node to check if it to has a child, until finally it hits a leaf node without children at which point it will move on to the next child node. This process goes on until every node has been hit and somewhat magically, all those 'return 1' gets added together and returned.
There is an element of trust required with recursion functions. I'm not quite sure how all those 1's were stored without a variable but I do know that it works. So I trust in it and I move on. Perhaps not the smartest thing, but it's working for me for the time being.
So this has been my summary or recursion. Hopefully I can come back to this post after a few weeks and have a lot more to say about recursion.
This has been an attempt to describe the indescribable.
Thanks and talk to you next week!
- Anisha Rohra
Before I begin, I would like to state that my definitions and explanations may not be entirely correct, as their main purpose is to describe the phenomenon of recursion, not necessarily to provide accurate definitions and explanations. In other words, I intend to be more colloquial than I probably ought to be.
So as I see it, recursion is the phenomenon of calling a function within its own code in order to avoid repetitive code and allow for deeper functions that do not rely on repeated for loops or unnecessarily long code. An example of a useful instance of recursive code is when dealing with class Tree- a sueful structure for several reasons, and unfortuneately requiring quite a bit of recusion.
Recursive functions require a base case. That is to say, the simplest situation in which no recursion is necessary. Often, this base case will be implemented frequently, at the end of every recursive call, so be careful when choosing both its condition and its code. Recursion base case looks like the following:
def count_nodes(tree):
if tree.children == []:
return 1
The code under the else clause will be the recusrive code. What we've learned so far is that there should be another function that is used to keep track of the information gathered in all the recursion calls. So in this example, if we are attempting to count the number of nodes in a tree, the else clause would look like the following:
else:
return 1 + sum([count_nodes(x) for x in tree.children])
What will happen here is that if the node that we've entered had no children, the function would return 1 for 1 node, the parent node. Otherwise, it returns 1 and then goes through each child node to check if it to has a child, until finally it hits a leaf node without children at which point it will move on to the next child node. This process goes on until every node has been hit and somewhat magically, all those 'return 1' gets added together and returned.
There is an element of trust required with recursion functions. I'm not quite sure how all those 1's were stored without a variable but I do know that it works. So I trust in it and I move on. Perhaps not the smartest thing, but it's working for me for the time being.
So this has been my summary or recursion. Hopefully I can come back to this post after a few weeks and have a lot more to say about recursion.
This has been an attempt to describe the indescribable.
Thanks and talk to you next week!
- Anisha Rohra
this element of trust is actually quite smart (or the leap of phase as the readings call it).
ReplyDelete