I&C SCI 32 Chapter 5: ICS 32 Website Notes- Recursion
23 Jun 2018
School
Department
Course
Professor
ICS 32 Fall 2015
Notes and Examples: Recursion
The problem
Summing the numbers in lists of integers
You've no doubt seen, in previous coursework, how to iterate over the elements of a list in Python using a for loop. For example,
given a list of integers, you could use the following function to calculate the sum of all of the integers in the list. (You could also use
the built-in sum function, but let's look at the detailed pattern; the nice thing about understanding the underlying pattern is that you
can use the pattern to solve similar problems for which there aren't built-in solutions like sum.)
sum_numbers1.py
def sum_numbers(numlist: [int]) -> int:
'''Adds up the integers in a list of integers'''
total = 0
for num in numlist:
total += num
return total
Now suppose we change the problem just slightly, so that we instead are given a list containing lists of integers (always two levels of
depth), but maintain the same goal of summing all of the integers. Our function changes somewhat, because we need to handle the
additional level of depth; we need to loop over the sublists in the list, then loop over the integers in the sublists.
sum_numbers2.py
def sum_numbers(numlist: [[int]]) -> int:
'''Adds up the integers in a list of lists of integers'''
total = 0
for sublist in numlist:
for num in sublist:
total += num
return total
So far so good. We can still solve the problem using tools we already have, though we did have to nest the for loops, so things have
gotten a bit more complicated. But one thing to notice is that the structure of the code follows the structure of the data we're
dealing with — the list is two levels deep, and the loops are nested two levels deep. (This is more common than you might think.)
To add one final twist to the problem, now let's assume we want to sum the numbers in a list whose elements are either integers or
lists of integers; so, in total, no more than two levels of depth. We can add the appropriate condition to our function to handle this
case, which requires only that we know that the function type(x) returns the type of the object x, and that we can compare types
using == to see if they're the same; that's a tool we could use to differentiate between the elements of the list that are integers and
the elements that are lists.
sum_numbers3.py
def sum_numbers(numlist: [int or [int]]) -> int:
'''
Adds up the integers in a list whose elements are either integers or
lists of integers
'''
total = 0
for element in numlist:
if type(element) == list:
for num in element:
total += num
else:
total += element
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
You"ve no doubt seen, in previous coursework, how to iterate over the elements of a list in python using a for loop. """adds up the integers in a list of integers""" total = 0 for num in numlist: total += num return total. Now suppose we change the problem just slightly, so that we instead are given a list containing lists of integers (always two levels of depth), but maintain the same goal of summing all of the integers. Our function changes somewhat, because we need to handle the additional level of depth; we need to loop over the sublists in the list, then loop over the integers in the sublists. sum_numbers2. py def sum_numbers(numlist: [[int]]) -> int: """adds up the integers in a list of lists of integers""" total = 0 for sublist in numlist: for num in sublist: total += num return total.
