CS 115 Lab 13, 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.

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.