←
Recursion with strings and lists

12.3 Recursion with strings and lists

Learning objectives

By the end of this section you should be able to

  • Demonstrate the use of recursion to solve a string problem.
  • Demonstrate the use of recursion to solve a list problem.
  • Use the built-in count() list function.

Recursion with strings

A word that is spelled the same forward and backward is called a palindrome. Ex: racecar.

Recursion can be used to identify whether a given word is a palindrome.

Checkpoint

Identifying a palindrome

Access multimedia content

Concepts in Practice

Recursion with strings

Refer to the animation above.

1.
Which of the following does palindrome() recognize as a palindrome?
  1. madamm
  2. madaM
  3. madame
2.
What would happen if the condition on line 4 of palindrome() is changed to if len(word) == 1:
  1. Only palindromes with an odd number of letters would be recognized correctly.
  2. Nothing. The function would work the same.
  3. The function would not recognize any palindromes.
3.
What would happen if the condition in line 8 palindrome() is changed to if palindrome(word.strip(word[0])).
  1. Nothing. The function would work the same: the first and last letter would be removed.
  2. Some words, such as "madamm", would be incorrectly recognized as a palindrome.

Recursion with lists

The animation below shows a recursive way to check whether two lists contain the same items but in different order.

The count() function returns a count of the number of items in a list that match the given item, and returns 0 otherwise. Ex: For list_num = [1, 3, 3, 4], list_num.count(3) returns 2.

Checkpoint

Checking list permutations

Access multimedia content

Concepts in Practice

List permutations

Refer to the above animation. What would permu_check() return for each pair of lists below?

4. 
list_num = [1, 7, 99, 2]
other_list = [99, 7, 1, 2]
  1. True
  2. False
5. 
list_num = [22, 9, 15, 17, 15]
other_list = [17, 9, 22, 22, 15]
  1. True
  2. False
6. 
honors_list = ["Bo", "Joe", "Sandy"]
first_names_of_team_1 = ["Sandy", "Bo", "Joe"]
  1. True
  2. False
7. 
this_list = [1, 2, [3], [4], 5]
that_list = [[3], 1, 5, [4], 2]
  1. True
  2. False
8. 
list_1 = [1, 2, 3]
list_2 = [1, 2, 3]
  1. True
  2. False

Try It

Remove duplicates

Write a recursive rem_dup() function that removes duplicates from a list.

Ex: List [5, 5, 2, 1, 3, 1, 6] should result in an output list [5, 2, 1, 3, 6].

Access multimedia content