This week I relied on other people for coming to terms with recursion; I found this lecture on Recursion, with eerie parallels to our class (N.B. the lecture is on Scratch, so code snobs may not approve). It gives a good summary of recursion, as well as new metaphors and bad jokes.
I also looked over berkey colortran's blog, which provided an example of backwards recursion to better understand it. At this point, I started to practice more elementary recursive functions, from the Python Practice Book, as well as Python course (which also mentions that without a base case, a recursive function could lead to an infinite loop).
Product using + and - operators only:
def product(num1, num2):
if num2 == 1:
return num1
else:
return num1 + product(num1, num2 - 1)
Flattening a list:
This was a bit hair wrenching for me, since it was more procedural:
1) check if an element is a list
2) a. flatten element if it is a list
b. append element if it is not a list
3) continue till list ends
def flatten_list(lst):
new_lst = []
for element in lst:
if isinstance(element, list):
for x in flatten_list(element):
new_lst.append(x)
else:
new_lst.append(element)
return new_lst
I traced this code to see if it would work:
lst = [1, [2, [3, 4]], 5]
def flatten_list(lst)
new_lst = [], element = 1
new_lst = [1], element = [2, [3, 4]]
| new_lst = [], element = 2
| new_lst = [2], element = [3, 4]
| | new_lst = [], element = 3
| | new_lst = [3], element = 4
| | new_lst = [3, 4]
| new_lst = [2], x = 3
| new_lst = [2, 3], x = 4
| new_lst = [2, 3, 4]
new_lst = [1], x = 2
new_lst = [1, 2], x = 3
new_lst = [1, 2, 3], x = 4
new_lst = [1, 2, 3, 4], element = 5
new_lst = [1, 2, 3, 4, 5]
So, it should work: but there is a lot of redundancy, and recursion seems moot here.
I printed the values for element and x in the shell:
>>> flatten_list([1, [2, [3, 4]], 5])
element is 1
element is [2, [3, 4]]
element is 2
element is [3, 4]
element is 3
element is 4
x is 3
x is 4
x is 2
x is 3
x is 4
element is 5
[1, 2, 3, 4, 5]
Back to the drawing board.
