Test 4 Review B

Problem R4b.1.

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

Problem R4b.2.

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

8
16
24
40

Problem R4b.3.

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 R4b.4.

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 R4b.5.

Without using loops (i.e., by using recursion), and also without using other functions or methods except len, create a function is_all_ms that takes a string parameter returns True if all characters in the string are the lower-case letter m and False otherwise. (When given the empty string, the result isn't important, as long as the function works for other strings.)

Problem R4b.6.

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

1
2
3
1
4
1
2

Problem R4b.7.

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

Problem R4b.8.

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 R4b.9.

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 R4b.10.

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:
        a = f(x - 1)
        return f(a + 1) + 1

Problem R4b.11.

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 R4b.12.

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