In addition to the concepts below, you should also know the concepts that were tested on all of the previous quizzes: Quiz 1, Quiz 2, Quiz 3, Quiz 4, Quiz 5.

You should be able to define and explain the following terms:

• The difference between recursion and iteration
• Base case
• Recursive case

You should understand and be able to use the following Python concepts:

• How variables are stored and function arguments are passed on the stack for recursive functions

Practice problems:

1. Write two versions of each of the following functions, one version using iteration and one using recursion:

   • sum all values in a given list of integers

   • return True if a list is sorted/in order, otherwise False

   • count/return how many times a given value (v) is found in a list (L)

   • find the largest number in a list

2. Draw a stack diagram for the following program. Show what the stack would look like at it's largest point.

   def main():
       n = 3
       ans = summation(n)
       print(ans)
   
   def summation(n):
       if n == 0:
          return 0
       else:
          return n + summation(n-1)
   
   main()
   

3. Show the output for the following program:

   def main():
       result = mystery("swarthmore")
       print(result)
   
   def mystery(x):
       if len(x) == 0:
           return ""
       elif x[0] == 'a':
           return '@' + mystery(x[1:])
       elif x[0] == 'e':
           return '3' + mystery(x[1:])
       elif x[0] == 'o':
           return '*' + mystery(x[1:])
       else:
           return x[0] + mystery(x[1:])
   
   main()
   

4. Here are several possible solutions to the problem of finding the product of a list of numbers. For example, product([4,2,5]) should return 40, which is equivalent to 4*2*5. Which of these solutions is correct? For incorrect solutions, what would be returned when each is called on the test list [4,2,5] and how would you fix the problem?

   def product1(ls):
       if len(ls) == 0:
           return 0
       else:
           return ls[0] * product1(ls[1:])
   
   def product2(ls):
       if len(ls) == 0:
           return 1
       else:
           return ls[0] * product2(ls)
   
   def product3(ls):
       if len(ls) == 0:
           return 1
       else:
           ls[0] * product3(ls[1:])
   
   def product4(ls):
       if len(ls) == 0:
           return 1
       else:
           return ls[0] * product4(ls[1:])