CSci 150: Foundations of computer science
Home Syllabus Readings Projects Tests

Test 4 Review B: Questions

R4b.1.

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

R4b.2.

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

def do_stuff(mn):
    if n > 0:
        do_stuff(nm % n)
        print(n)
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.

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.

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.)

R4b.6.

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

def print_stuff(n):
    if n > 0:
        print_stuff(n - 1)
        print(n)
        print_stuff(n - 2)
R4b.7.

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

def f(a):
    if a >= 5:
        return a
    else:
        b = f(a + 1)
        c = f(a + 2)
        return b + c
R4b.8.

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

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

Also, what number does this function return?

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)
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
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?

R4b.12.

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

def f(n):
    k = 1
    for i in range(2n - 1):
        if n % i == 0:
            k += f(i)
    return k

Test 4 Review B: Solutions

R4b.1.

The base case is a situation in which a recursive function does not perform any recursive invocations. Without any base case, a recursive function will recurse indefinitely, until the program runs out of memory, whereupon it will abort.

R4b.2.
8
16
24
40
R4b.3.
def count_down(n):
    print(n)
    if n > 0:
        count_down(n - 1)
R4b.4.
def halvings(n):
    if n == 1:
        return 0
    else:
        return 1 + halvings(n // 2)
R4b.5.
def is_all_ms(word):
    if len(word) <= 1:
        return word == 'm'
    elif word[0] == 'm':
        return is_all_ms(word[1:])
    else:
        return False
R4b.6.
1
2
3
1
4
1
2
R4b.7.
R4b.8.

The function returns 11.

R4b.9.

R4b.10.
R4b.11.

It returns 17.

R4b.12.