Section 1: Designing with loops

 Table of Contents > Chapter 3 > Section 1 

The template for a function that consumes a (listof X) and that processes the list using a loop rather than natural recursion is as follows:

def fn_for_lox(lox):

    acc = ...

    for x in lox:
        ...x

        acc = ...x ...acc

    return ...acc

The construct for x in lox: should be read "for each x in lox do something". The particular something that we want to do is specified by the indented block of code following the colon.  In this case, we can optionally do something with x and we will want to update the value of acc by doing something with x and the current value of acc.  The variable acc is used to accumulate whatever value is needed as we process the loop.  Note that in some cases, more than one accumulator may be needed.

If you have already designed a function using tail recursion and an accumulator, redesigning the code using a loop is relatively straightforward.  We illustrate this process for our sum_loi function in Screencast 3.1.   The final version of this code is presented in Code Explorer 3.1. 

So now let's see what happens when we try to sum the entries in a list that contains a large amount of data:


As we are no longer making recursive calls to our function, we are not limited by the depth of recursion imposed by the Python interpreter and can process data that is much larger.

Note that sometimes we will design a function using natural recursion.  We may then find that the size of the data causes the maximum depth of recursion to be exceeded, in which case we re-factor the design to use a loop.  In other cases, we may start by designing the function using a loop.

Example

Suppose we want to design a function that consumes a list of integers and a threshold value, and determines how many integers in the list are below the threshold.  If we are to design a solution using a loop, we must determine what we need to accumulate as the list is processed.  In this case, we need to keep track of how many of the integers processed so far are below the given threshold value. 

It is often helpful to walk through an example so that you can see how the necessary values are accumulated as the list is processed.  Let's assume that we want to determine how many entries in the list [4, -3, 0, 6, 8] are below the threshold value of 4. 



Recall that the Python for-each loop will successively provide us with the next item to be processed in the list.  We need to determine what it is that we wish to accumulate as we process the list.  In this case, we want to accumulate the number of items in the list that are below the threshold value, so we'll use an accumulator count_below initialized with the value 0 for this purpose.  Then,  for each value in the list, we determine if that value is below the threshold value of 4.  If it is, we add one to the accumulator count_below, otherwise we simply move on to the next item in the list.  The final version of this code is presented in Code Explorer 3.2.