Recursion in Python (Part 2)

Example 1: raises with more than one input

What about a function with more than one input? Here we have a list of salaries and a booster, which we'll use to determine new salaries. If we already had the function from the future, all we would need to do would be to multiply the first salary by the booster, put it in a list, and then concatenate the result of using the function on the rest of the list. Here are the key points to remember: booster must be included as a parameter, since the function takes two inputs. This is the only way of communicating the value of booster to the function call. booster does not change in any of the calls, even though the list does.

## [salaries[0] * booster] + \
## change(salaries[1:], booster)

We multiply the first salary by the booster, put it in a list, and concatenate the result of using the function on the rest of the list.

---

def change(salaries, booster):

We now write the function header, making sure to have two parameters.

---

    if len(salaries) == 0:
        return []

Our base case is the empty list. Since we're returning a list, in this case it is the empty list that we return.

---

    else:
        return [salaries[0] * booster] + \
               change(salaries[1:], booster)

For the recursive case, we use the expression we formed.

---

def test_change():
    the_list = [4, 3, 5, 2, 1]
    assert change(the_list, 2) == [8, 6, 10, 4, 2]
    assert the_list == [4, 3, 5, 2, 1]
    assert change([], 2) == []

test_change()

We make sure to have tests with both empty and non-empty lists.

---

Here's our function when all parts are put together:

## [salaries[0] * booster] + \
## change(salaries[1:], booster)

def change(salaries, booster):
    if len(salaries) == 0:
        return []
    else:
        return [salaries[0] * booster] + \
               change(salaries[1:], booster)

def test_change():
    the_list = [4, 3, 5, 2, 1]
    assert change(the_list, 2) == [8, 6, 10, 4, 2]
    assert the_list == [4, 3, 5, 2, 1]
    assert change([], 2) == []

test_change()

---

Example 2: raises with lists as inputs

What if we wanted to have a function that processed a list of salaries and also a list of boosters?

## [salaries[0] * boosters[0]] + \
## change(salaries[1:],boosters[1:])

We change both lists in our function call.

---

def change(salaries, boosters):

Again, we have two inputs whenever we use the function, and of course also when we define it.

---

    if len(salaries) == 0:
        return []

Again, the base case is the empty list.

---

    else:
        return [salaries[0] * boosters[0]] + \
               change(salaries[1:],boosters[1:])

The recursive case uses the expression we developed.

---

def test_change():
    """Tests correctness of change
    """
    assert change([],[]) == []
    assert change([2, 3], [4, 5]) == [8, 15]

test_change()

As usual, we have tests for both empty and non-empty lists.

---

Here's our code when all parts are put together:

## [salaries[0] * boosters[0]] + \
## change(salaries[1:],boosters[1:])

def change(salaries, boosters):
    if len(salaries) == 0:
        return []
    else:
        return [salaries[0] * boosters[0]] + \
               change(salaries[1:],boosters[1:])

def test_change():
    """Tests correctness of change
    """
    assert change([],[]) == []
    assert change([2, 3], [4, 5]) == [8, 15]

test_change()

We chose to set up our recursion to look at the first item separately from the rest of the list. If we had looked at the last item instead, we could have used append instead of concatenation to form the new list. This isn't an issue in this course, but worth considering for when you advance in your programming.

---

Example 3: determining if two lists are equal

For our last example, let's again process two lists, this time finding out if they are equal. This is a little different from the last question, in which we knew the lists were of the same length. Here anything is possible. We first figure out how we can use recursion. If we have a function that can determine if two lists are equal, we need to compare the first items in the lists and then make sure the rest of the lists are equal. This is another example in which both lists change in the function call.

## one[0] == two[0] and \
## equal(one[1:], two[1:])

We process two lists and find out if they are equal.

---

def equal(one, two):

We create the header.

---

    if len(one) == len(two) == 0:
        return True

Observe that if both lists are of length zero, then they are equal. But it isn't yet safe to use the expression we created, since it is still possible that one of the lists is empty. That would result in an error because of our use of the index function.

---

    elif len(one) == 0 or len(two) == 0:
        return False

So we can check to see if either one has length zero. Since the first condition is False, we know that if the second condition is True, exactly one list has length zero, meaning that they are not equal.

---

    else:
        return one[0] == two[0] and \
               equal(one[1:], two[1:])

We can now use our expression.

---

def test_equal():
    assert equal([],[]) == True
    assert equal([],[1]) == False
    assert equal([1],[]) == False
    assert equal([1, 2, 3], [1, 2]) == False
    assert equal([1, 2], [1, 2, 3]) == False
    assert equal([1, 2, 4], [1, 2, 3]) == False
    assert equal([1, 2, 3], [1, 2, 3]) == True

test_equal()

We check to see that our function works properly on all cases.

---

Here's our function when all parts are put together:

## one[0] == two[0] and \
## equal(one[1:], two[1:])


def equal(one, two):
    if len(one) == len(two) == 0:
        return True
    elif len(one) == 0 or len(two) == 0:
        return False
    else:
        return one[0] == two[0] and \
               equal(one[1:], two[1:])

def test_equal():
    assert equal([],[]) == True
    assert equal([],[1]) == False
    assert equal([1],[]) == False
    assert equal([1, 2, 3], [1, 2]) == False
    assert equal([1, 2], [1, 2, 3]) == False
    assert equal([1, 2, 4], [1, 2, 3]) == False
    assert equal([1, 2, 3], [1, 2, 3]) == True

test_equal()

---