Quiz 3 Review

Problem Q3r.1.

Define the term base case as it applies to recursive functions. Why is a base case necessary?

Problem Q3r.2.

If the below function is invoked as do_stuff(64, 40), what does the function display?

8
16
24
40

Problem Q3r.3.

If the below function is invoked as print_stuff(4), what does the function display?

1
2
3
1
4
1
2

Problem Q3r.4.

Draw a recursion tree representing the recursive calls made when computing the value of f(4, 2) using the following function.

def f(n, r):
    if r == 0 or n == r:
        return 1
    else:
        return 1 + f(n - 1, r - 1) + f(n - 1, r)

Also, what number does this function return?

The function returns 11.

Problem Q3r.5.

Draw a recursion tree representing the recursive calls made when computing the value of f(11) using the following function.

def f(n):
    if n <= 1:
        return 1
    elif n % 2 == 0:
        return 2 * f(n / 2)
    else:
        return f((n - 1) / 2) + f((n + 1) / 2)

Problem Q3r.6.

Draw a recursion tree representing the recursive calls made when computing the value of f(17) using the following function.

def f(x):
    if x == 1:
        return 0
    elif x % 2 == 0:
        return f(x / 2) + 1
    else:
        return f(f(x - 1) + 1) + 1

Problem Q3r.7.

Draw a recursion tree representing the recursive calls made when computing the value of f(5) using the following function.

def f(n):
    k = n
    i = 1
    while i < n:
        k += f(i)
        i = 2 * i
    return k

Also, what number does f(5) return?

It returns 17.

Problem Q3r.8.

Without using loops (i.e., by using recursion), create a function count_down that displays all the integers from its parameter down to 0 (and including 0). The result should be that the function call count_down(10) displays the integers from 10 down to and including 0.

Problem Q3r.9.

Without using loops (i.e., by using recursion), write a function stutter that takes a string parameter and returns a string containing the first letter, followed by the first two letters, then the first three letters, and so on until you get the entire word. For example, given tar as a parameter, the function should compute t-ta-tar to arrive at the string ttatar. Thus, a call to stutter("tar") should return ttatar.

Problem Q3r.10.

Without using loops (i.e., by using recursion), write a function harm so that it computes the nth harmonic number. (Recall that the nth harmonic number is the sum of the reciprocals of the integers from 1 to n; for example, the 3rd harmonic number is 1/1 + 1/2 + 1/3 = 1.8333….)

Problem Q3r.11.

Without using loops (i.e., by using recursion), write a function halvings that takes an integer parameter and returns the number of times that integer can be halved before reaching 1 (rounding down for odd integers). For example, halvings(10) should return 3, since the sequence would be 10 → 5 → 2 → 1, which involves three halvings.

Problem Q3r.12.

Without using loops or built-in functions (i.e., by using recursion), complete the following Python function so that it finds the sum of the first count numbers from the parameter list nums.

Problem Q3r.13.

Suppose we represent a person's ancestor using a list, starting with the person's name in the first element, then a representation of the father in the second element, and then a representation of the mother in the third. Both the father and the mother are themselves represented as lists: If the parent's parents are unknown, the list could have just a single string giving the parent's name; but if the parent's parents are known, the list will itself start with the parent's name followed by the father's representation followed by the mother's representation. As an example, below is a representation of the ancestors of Albus Potter, son of Harry Potter and Ginny Weasley.

['Albus',
    ['Harry', ['James'], ['Lily']],
    ['Ginevra', ['Arthur', ['Septimus'], ['Cedrella']], ['Molly']]]

Write a function count_ancestors that takes such a list as a parameter and returns the number of names that appear in the list. For the above example, it should return 9.