Recursion is perhaps one of the more interesting parts of programming as it manages to simplify processes that would otherwise be more convoluted to code. It focuses on using properties already displayed in a function again when a certain case comes up. Recursive functions are very helpful for going over nested lists or tuples, restarting games or when a while loop is too inconvenient or complicated to be implemented. I had already messed around with a sort of simple version of recursion before, which I'll demonstrate in this first function.
def recurs(n):
if n % 2 == 1 and n < 16:
if n in [11, 13, 15]:
n = n - 7
print(n)
recurs(n)
else:
n = abs(n) * 2
print(n)
recurs(n)
elif n % 2 == 0 and n < 16:
n = n - 11
print(n)
recurs(n)
else:
print(str(n) + ' is greater than 16')
This function has the interesting property of printing each number that goes through its designated step and returning '18 is greater than 16' for any number below 16. For example, recurs(7) produces:
14
3
6
-5
10
-1
2
-9
18
18 is greater than 16
It's easy for anyone to see that the function could very well just be a while loop, but it's fun to play around with this sort of style of repeating steps. But let's start going with functions that are more reminiscent of work we've done in class/labs.
def sumlen(L):
""" (arbitrarily nested list of int) -> int
Return the sum of the ints in the list divided by the length of the list
"""
if isinstance(L, list):
return int(sum([sumlen(x) for x in L]) / len(L))
else:
return L
The docstring clearly explains what the function does, and for the sake of analyzation, we'll look at some examples on how this function works.
>>> sumlen([1, 2, 3])
The list's sum is 1+2+3 and the length is 3. 6 / 3 = 2.
>>> sumlen([10, [1, 2, 3], 3])
We have inside a recursive list. The whole list is length 3 and the inner list is length 3. Since we already calculated it's value, we know that what we're adding is 10+2+3 which divided by 3 would produce 5.
>>> sumlen([1, [2, 3, [4, 5], 6], 7, 9])
Now we have a recursive list of depth 2. First we'd concern ourselves with the most inner list which is int((4+5)/2) = 4. Now the 1st-depth inner list results in int((2+3+4+6)/4) = 3. This leaves with the list as [1, 3, 7, 9] which is (1+3+7+9)/4 = 5.
>>> sumlen([1, [1, 3], 2, [10, 15, 2], 3])
Again, we consider the inner lists first and then the whole list. The whole list would be [1, 2, 2, 9, 3] whose sum is 17 and divided by 5 and floored (or converted to an int) results in 3.
Here we have a more complicated function.
def negative_hiccup(L):
""" (arbitrarily nested list of int) -> int
Consider a man who adds two numbers, but then subtracts the third
number, following a pattern of (0 + a + b - c + d + e - f...). Return
an int based on this pattern.
"""
result = 0
for i in range(len(L)):
if i % 3 == 0 or i % 3 == 1:
if isinstance(L[i], list):
result = result + negative_hiccup(L[i])
else:
result = result + L[i]
else:
if isinstance(L[i], list):
result = result - negative_hiccup(L[i])
else:
result = result - L[i]
return result
Technically, we could have converted this into a helper function for just a list and then used it recursively if we wanted it to consider it for a recursive list, but this is still a valid way of implementing it. Let's look at the examples.
>>> negative_hiccup([4])
This is simply 4 as the first item is added to 0.
>>> negative_hiccup([4, 1])
The pattern goes 0 + 4 + 1, so it results in 5.
>>> negative_hiccup([4, 1, 5])
As a reminder, when we have the third item (or an item in an index which % by 3 results in 2), we subtract it from the total, so 0 + 4 + 1 - 5 results in 0.
>>> negative_hiccup([4, 1, 5, 2])
Again, we know the pattern, so it'll just be 2. Where's the fun stuff?!
>>> negative_hiccup([4, 1, [5, 2]])
Ah! Now we've got something going on. See, when we hit index 2, the function considers the list as the start of another negative-hiccup calculation, adding 5 and 2 to 0. This makes the whole list [4, 1, 7]. So now when negative_hiccup looks over the whole list, it simply subtracts 7, leaving -2.
>>> negative_hiccup([4, 1, 5, 2, 3])
Gah, boring stuff again! It's 5! Next!
>>> negative_hiccup([4, 1, [5, 2, 3]])
Now, we're back to same example in which we just go through the pattern anew on the list. This time it's 0 + 5 + 2 - 3 which results in the whole list being [4, 1, 4], resulting in 1.
>>> negative_hiccup([4, 1, 5, 2, 3, 10])
Okay, back to this tripe, it's -5!
>>> negative_hiccup([4, [1, 5], 2, [3, 10]])
By now we know what to do with those inner lists, so we basically would go like this:
0 + 4 + (1 + 5) - 2 + (3 + 10) = 0 + 4 + 6 - 2 + 13 = 21
>>> negative_hiccup([4, [1, [5, 2, 3], 10]])
Oh! Now we got a deeper list to look at. By now we know we start with 4, but in the second index, we have [1, [5, 2, 3], 10]. We would have to go by the negative-hiccup calculation in the second index's inner list which result in the second index being reduced to [1, 4, 10] which equals -5. When added to 4, we get -1.
>>> negative_hiccup([45, [10, 17, [8, 9, 5], [15, [19, 32, [27, [5, 2, [3, 7, 2]], 39], 11], 10, 48], 33], 6, 24, 10, [5, 24]])
Uh...let's just say 220 and leave it at that.
So, there you have a little bit of recursive function fun!
##########################################################################
Object Oriented Programming Concept Summary:
- Object Oriented Programming is focused on using custom classes with various special methods and properties included, some of which serve as Abstract Data Types (like lists, stacks, queues, trees).
- Stacks follow a First In Last Out format in which objects are pushed to the top and then popped when necessary. It's easy to think of a stack because one can imagine a pile of books used for a project. You get the one on the top, use it's information and then follow with the next one.
- Queues follow a First In First Out format in which objects are enqueued into a queue and then dequequed when necessary. A very prominent example of a queue is a playlist. No matter what you add to it, the song you put in first plays.
- Trees are constructed with nodes, some which have children and others which do not (called leaves). A tree is a very useful ADT to visualize as based on the logic one applies to it, it can lead one to understand the relationship between a node and its children. Trees require an understanding of recursion as they are far more complex to implement than both stacks and queues.
