CSCI 150: PreLab 8 Answer Key

Recursion

In this optional prelab (you do not have to turn this in, it is just an additional resource), we will formulate some of the ideas necessary to complete Lab 08.

Recursive Output

For the following two problems, you'll work out by hand the result of method invocations of the following two recursive methods.

Function strange


  def strange(x) :
    if x <= 0 :
       return 1
    else :
       return 5 * strange(x-1) - 2

Function weird


  def weird(x) :
    if x > 0 :
       print(x,"",end='')
       if x%2 == 0 :
          weird(x-3)
          weird(x-2)
       else :
          weird(x-1)

1. What is the output of print(strange(3))

Answer:
strange(3) = 63 since

strange(0) = 1
strange(1) = 5 * strange(0) - 2 = 5 * 1 - 2 = 3
strange(2) = 5 * strange(1) - 2 = 5 * 3 - 2 = 13
strange(3) = 5 * strange(2) - 2 = 5 * 13 - 2 = 632. What is the output of weird(8) Answer: 8 5 4 1 2 6 3 2 4 1 2

Part 1 - Recursion with Numbers As we have seen (or will have seen, depending on when you're looking at this), the factorial function can be computed not only using a loop, but via recursion as well. Recall the the typical definition of factorial looks something like this: 0! = 1, 1! = 1, 2! = 2*1 = 2 and 3! = 3*2*1 = 6, and in general, n! = n*(n-1)*...*3*2*1. But we could also define the factorial function recursively as follows. We'll use fact(n) to denote our recursive representation of n!. We'll define fact(n) = 1 when n is 0 and fact(n) = n*fact(n-1) otherwise. If you think about it, fact(n) gives the exact same values as n!. 3. Give an analogous definition for n^k (n raised to the power of k). That is, you should define power(n,k) = ??? when k = ??? and power(n,k) = ??? otherwise. The last component you need to fill in should involve a recursive call to power. No loops or ** operator! Answer: power(n, 0) = 1 [the base case] power(n, k) = n * power(n, k-1) [the recursive call] 4. Give an analogous recursive definition for the sum of the first n perfect squares. For example, your definition should satisfy sps(1) = 1, sps(2) = 1 + 4 = 5, and sps(3) = 1 + 4 + 9 = 14. No loops! Answer: sps(0) = 0 [the base case] sps(n) = n * n + sps(n-1) [the recursive call] Part 2 - Recursion with Strings Here is pseudocode for recursively printing a string s in reverse If the length of s is 0, do nothing Otherwise, print the last letter of s and reverse s with the last letter removed. 5. Give pseudocode for a single function that recursively determines whether a string s is a palindrome (the same forwards as backwards, like "racecar"). You can find the length of s, look up characters in s, and get slices of s, but you should not use any loops or the reverse() function that sequences have. Answer: If the length of s is 0 or 1, return True. Else if the first and last characters in s are not the same, return False. Otherwise, remove the first and last letter from s (using new_s = s[1:-1]) and return whether or not the new_s is a palendrome. Part 3 - Fractal Images Consider the following figure. Let A_x and A_y denote the x and y coordinates of the corner labelled A in the large triangle above. Let B_x, B_y, C_x and C_y be definied similarly. Assume P, Q and R each lie at the midpoint of their corresponding edge in the triangle ABC. 6. Specify the x and y coordinates of P, Q and R in terms of A, B and C's x and y coordinates. Do not assume that any coordinates are 0 or that there is any relationship between the points (the triangle ABC pictured happens to be fairly symmetric, but you shouldn't assume this will necessarily be the case). Answer: P is the midpoint between A and C, so P_x = (A_x + C_x) // 2 and P_y = (A_y + C_y) // 2 Q is the midpoint between B and C, so Q_x = (B_x + C_x) // 2 and Q_y = (B_y + C_y) // 2 R is the midpoint between A and B, so R_x = (A_x + B_x) // 2 and R_y = (A_y + B_y) // 2 Honor Code If you followed the Honor Code in this assignment, write the following sentence attesting to the fact at the top of your homework. I affirm that I have adhered to the Honor Code in this assignment.