Menu
Home
Log in / Register
 
Home arrow Computer Science arrow Data Structures and Algorithms with Python
< Prev   CONTENTS   Next >

3.7.2 Reversing a List

1 def revList(lst):

2 # Here is the base case

3 if lst == []:

4 return []

5

6 # The rest of this function is the recursive case.

7 # This works because we called it on something smaller.

8 # The lst[1:] is a slice of all but the first item in lst.

9 restrev = revList(lst[1:])

10 first = lst[0:1]

11

12 # Now put the pieces together.

13 result = restrev + first

14

15 return result

16

17

18 def main():

19 print(revList([1,2,3,4]))

20

21 if name == " main ":

22 main()

You can write recursive functions that work with strings too. Strings and lists are both sequences. In the code of Sect. 3.7.2 we made sure we recursively called our function on something smaller. The same is true when working with strings. A string reverse function is given in Sect. 3.7.3.

3.7.3 Reversing a String

1 def revString(s):

2 if s == "":

3 return ""

4

5 restrev = revString(s[1:])

6 first = s[0:1]

7 # Now put the pieces together.

8 result = restrev + first

9

10 return result

11

12

13 def main():

14 print(revString("hello"))

15

16 if name == " main ":

17 main()

Notice the similarity of these two functions. The functions are nearly identical. That's because the recursive definition of reverse did not change. The only change is that we must use the string concatenation operator instead of the list concatenation operator and the empty string instead of the empty list.

3.7.4 Another Version of Reverse

1 def revList2(lst):

2

3 def revListHelper(index):

4 if index == -1:

5 return []

6

7 restrev = revListHelper(index-1)

8 first = [lst[index]]

9

10 # Now put the pieces together.

11 result = first + restrev

12

13 return result

14

15 # this is the one line of code for the

16 # revList2 function.

17 return revListHelper(len(lst)-1)

18

19

20 def main():

21 print(revList2([1,2,3,4]))

22

23 if name == " main ":

24 main()

The examples in Sects. 3.7.2 and 3.7.3 used slicing to make the list or string smaller on each recursive call. It is possible to make a list or string smaller without actually making it physically smaller. Using an index to keep track of your position within a list can serve to make the list or string smaller. In that case it may be helpful to write a function that calls a helper function to do the recursion. Consider the program in Sect. 3.7.4. This code uses a nested helper function called revListHelper to do the actual recursion. The list itself does not get smaller in the helper function.

Instead, the index argument gets smaller, counting down to −1 when the empty list is returned. The revList2 function contains only one line of code to call the revListHelper function.

Because the revListHelper function is nested inside revList2 the helper function is not visible to anything but the revList2 function since we don't want other programmers to call the helper function except by calling the revList2 function first.

It is important to note that you don't have to physically make a list or string smaller to use it in a recursive function. As long as indexing is available to you, a recursive function can make use of an index into a list or string and the index can get smaller on each recursive call.

One other thing to note. In this example the index gets smaller by approaching zero on each recursive call. There are other ways for the argument to the recursive function to get smaller. For instance, this example could be rewritten so the index grows toward the length of the list. In that case the distance between the index and the length of the list is the value that would get smaller on each recursive call.

 
Found a mistake? Please highlight the word and press Shift + Enter  
< Prev   CONTENTS   Next >
 
Subjects
Accounting
Business & Finance
Communication
Computer Science
Economics
Education
Engineering
Environment
Geography
Health
History
Language & Literature
Law
Management
Marketing
Philosophy
Political science
Psychology
Religion
Sociology
Travel