printable version
Test 4 Review B
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]
[12]
Problem R4b.1.
Define the term base case as it applies to recursive
functions. Why is a base case necessary?
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.
Problem R4b.2.
If the below function is invoked as do_stuff(64, 40)
, what
does the function display?
def do_stuff(m, n):
if n > 0:
do_stuff(n, m % n)
print(n)
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.
def count_down(n):
print(n)
if n > 0:
count_down(n - 1)
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.
def halvings(n):
if n == 1:
return 0
else:
return 1 + halvings(n // 2)
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.)
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
Problem 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)
Problem 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
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.
def f(n):
k = 1
for i in range(2, n - 1):
if n % i == 0:
k += f(i)
return k