CS 115 Lab 14, Part A: Recursion practice

[Back to lab instructions]

Before you start writing your own code, you'll use the the online Python 3 tutor to trace the execution of recursive functions. Try to predict what will happen before stepping through the code in the tutor.

This part is important to understand how recursion works- there is usually a similar question in Exam 3!!

1. Enter the following code into the tutor:

   def f(x):
       if x <= 1: return 1
       temp = f(x - 1)
       return x * temp
   
   
   def main():
       a = f(4) # Statement 1
   
   
   main()
       

2. Trace through the execution of Statement 1, and answer Question 1 in the writeup.
3. Enter the following code into the tutor:

   def reverse(s):
       if len(s) <= 1: return s
       return s[-1] + reverse(s[0:-1])
   
   
   def main():
       a = reverse('H') # Statement 1
       b = reverse('seawolf') # Statement 2
   
   
   main()
       

4. Trace through the execution of Statement 2, and answer Question 2 in the writeup.
5. Enter the following code into the tutor:

   def mystery(x):
       if x == 0: return 0
       return (x % 10) + mystery(x // 10)
   
   
   def main():
       a = mystery(46213)
   
   
   main()
       

6. Trace through the execution of the function calls, and answer Questions 3 and 4 in your writeup.
7. Enter the following code into the tutor:

   def mystery2(L, i):
       if len(L) <= i: return 0
       return L[i] + mystery2(L, i + 1)
   
   
   def mystery1(L):
       return mystery2(L, 0)
   
   
   def main():
       a = mystery1([4, 10, 1, 3])
   
   
   main()
   

8. Trace through the execution of the function calls, and answer Questions 5 and 6 in your writeup.
9. Continue to Part B.