Define the term base case as it applies to recursive functions. Why is a base case necessary?
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)
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.
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.
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.)
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)
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
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?
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)
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
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?
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
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.
8 16 24 40
def count_down(n):
print(n)
if n > 0:
count_down(n - 1)
def halvings(n):
if n == 1:
return 0
else:
return 1 + halvings(n // 2)
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
1 2 3 1 4 1 2
The function returns 11.
It returns 17.