15110 Ruby Drills
David S. Touretzky
Work in progress; check back for updates.
Added: answers to all the problems (11/22); click to expose
Added: recursion on trees (11/22)
Added: recursion on integers (10/27)
print vs. return
 What is the difference between print and return?
Answer
print displays a value on the terminal; return terminates a
function's execution and supplies a return value to whoever called the function.
 What value does print return?
Answer
print returns nil.
 If a method does not execute a return statement, what value does it return?
Answer
It returns the value of the last expression it executed.
 What do each of the following functions do when called
on the list [1,2,3,4,5]?
def f1(list)
for x in list do
print x if x.odd?
end
end

def f2(list)
for x in list do
return x if x.odd?
end
end

Answer
f1 prints 135 and returns [1,2,3,4,5] because that is the value of the for statement. f2 returns 1.
 What values do f1 and f2 return for the input [1,2,3,4,5]?
Answer
f1 returns [1,2,3,4,5], while f2 returns 1.
 What values do f1 and f2 return for the input [2,4,6,8]?
Answer
Both functions return [2,4,6,8], because neither executes a return statement.
 Fill in the blanks:
 When we want to go through a list to search for an element that
passes a test, and stop searching as soon as we have found it, we
should use _________ to exit the loop and deliver the element as the
result of the function.
Answer
return
 When we want to go through a list and display all the elements that
pass a test, we should use _________ to display each element.
Answer
print
 The _________ statement always produces output on the console.
Answer
print
 The _________ statement specifies the result of the function
containing it. That result may or may not be displaed on the console,
depending on the context in which the function is being called.
Answer
return
Lists
 Given x = ["b", "c", "d"], write a short Ruby expression
to produce each of the following results. Your expression can include
x, a quoted string, the + operator, and/or brackets and commas for
constructing lists. You may not use the << operator.
 ["a", "b", "c", "d"]
Answer
["a"] + x
 ["b", "c", "d", "e"]
Answer
x + ["e"]
 [["b", "c", "d"]]
Answer
[x]
 ["a", ["b", "c", "d"]]
Answer
["a", x]
 ["b", "c", "d", "b", "c", "d"]
Answer
x + x
 [["b", "c", "d"], ["b", "c", "d"]]
Answer
[x,x]
 ["b", "c", "d", ["b", "c", "d"]]
Answer
x + [x]
 Given x = ["b", "c", "d"], write a short Ruby expression
using collect to produce each of the following results:
 [["a", "b"], ["a", "c"], ["a", "d"]]
Answer
x.collect {e ["a",e]}
 ["bb", "cc", "dd"]
Answer
x.collect {e e+e}
 [[["b"]], [["c"]], [["d"]]]
Answer
x.collect {e [[e]]}
Recursion
Read the Dragon
stories (sections 8.1, 8.2, 8.4, 8.6, 8.8, and 8.9) to help you
understand recursive thinking.
Thinking Recursively
To solve a problem recursively you must answer three questions:
 What is the base case? This question asks how will we
recognize an input for which we should not make a recursive call? Is
it zero? The empty list? A nonlist value? Pick the simplest base
case you can. Often, for list problems, this will be the empty list,
but that's not always the case.
 How can I derive a smaller problem from this one? For
numbers, this often means subtracting one from the input. For flat
(nonnested) lists, it may mean removing the first element from the
input and recursing on what's left. For nested lists (e.g., trees) it
may mean recursing on the first element of the input, and then perhaps
recursing again on everything except the first element.
 How can I make progress with each recursive call? Making
progress might mean doing something with the input, or with the result
you got back from the recursive call, or both.
Let's try an example: write a recursive function f(n) to
print a row of n asterisks, followed by a newline, and return
nil. Example:
>> f(8)
********
=> nil
Let's work through our three questions:
 What should the base case be? ___________
Answer
n is 0.
 Given an input n, how can you make a smaller
problem from this one? _________________
Answer
Replace n by n1.
 How can you make progress with each recursive call? Think about
it this way: if your job is to print eight asterisks, and you can get
somebody else to print the last seven of them, then what do you need
to do yourself? __________________
Answer
Print one asterisk.
Here is Ruby code to solve the problem. For each of the three
questions above, write that number on the line that implements your
answer to that question.
def print_asterisks(n)
if n == 0 then ____
print "\n"
else
print "*" ____
print_asterisks(n1) ____
end
Answer
i, iii, ii
Breaking A Problem Down
The neat thing about looping is that you can solve an arbitrarily
complex problem by just doing one relatively simple thing over and
over. This is true both for recursion and iteration; the difference
is in how you break the problem down:
 When we iterate over a list, using for or
while, we always have the complete list available, and we use
an index variable i to move across the elements, writing
list[i] to get to the element we're currently operating on.
 When we recurse over a list, we don't use an index
variable. Instead, we generate a series of recursive calls on smaller
and smaller lists by eliminating some elements each time, and making a
tiny bit of progress before or after each recursive call.
If it's not clear how to break down a particular list processing
problem recursively, here's an interesting way to approach the
question. Pick an example list and write down expressions to access
each of the elements your function needs to examine. Then look for a
pattern.
For example: suppose x = ["apple", "banana", "cherry",
"date"] and we want a function to print each element followed by
the string " pie", on a separate line, producing:
apple pie
banana pie
cherry pie
date pie
We could do this for the first element by writing:
puts x.first + " pie"
Since we're trying to come up with a recursive solution, we don't want
to use subscripting to access later elements; we want to construct
smaller lists. We can use drop(1) to
nondestructively remove the first element of a list and return what's
left, so for banana pie we could do:
puts x.drop(1).first + " pie"
For the third and fourth elements we would do:
puts x.drop(1).drop(1).first + " pie"
puts x.drop(1).drop(1).drop(1).first + " pie"
Now you can see a pattern: we are dropping one more element each time
we move to the next position in the list. We still only have one call
to first and one use of + at the end. It's the
drop(1) part that repeats, so this is the part that will be
in the recursive call. We'll use first and + in the
portion of the function where we make a little bit of progress each
time. Now all we need is the base case, which obviously should be the
empty list. Thus, the solution to our problem is:
def print_pies(list)
if list.empty? then # base case
return nil
else
puts list.first + " pie" # make a little bit of progress
print_reversed(list.drop(1)) # recurse on a smaller problem
end
end
Now suppose we want to print the items in the reverse order, like this:
date pie
cherry pie
banana pie
apple pie
We can do this simply by making the recursive call before the
"make a little progress" step instead of after it:
def print_reversed_pies(list)
if list.empty? then # base case
return nil
else
print_reversed_pies(list.drop(1)) # recurse on a smaller problem
puts list.first + " pie" # make a little bit of progress
end
end
If you don't see why this program works, try inserting a puts
"list = " + list.inspect statement at the beginning of
the function to trace the recursion.
Recursion on Lists
 Write a recursive function to print out each element of a
list of numbers on a line by itself. Hint: print the first element,
then call recursively.
Answer
def f(list)
if not list.empty? then
puts list[0]
f(list.drop(1))
end
end
 Write a recursive function to print out each element of a
list on a line by itself, in reverse order (the last element is
printed first). Hint: do the recursive call first, then print the
first element.
Answer
def f(list)
if not list.empty? then
f(list.drop(1))
puts list[0]
end
end
 Write a recursive function to add up all the elements of a
list of numbers.
Answer
def f(list)
if list.empty? then
return 0
else
return list[0] + f(list.drop(1))
end
end
 Write a recursive function to return the first odd number in a list.
Answer
def f(list)
if list.empty? then
return nil
elsif list[0].odd? then
return list[0]
else
return f(list.drop(1))
end
end
 Write a recursive function to return a list of all the odd
numbers in its input, e.g., f([1,2,3,4,5,6]) should return [1,3,5].
Answer
def f(list)
if list.empty? then
return []
elsif list[0].odd? then
return [list[0]] + f(list.drop(1))
else
return f(list.drop(1))
end
end
 Write a recursive function to return the last element of a
nonempty list. Note: you can do this nonrecursively by writing
list.last or list[1] or
list[list.length1], but the idea here is to do it
recursively.
Answer
def f(list)
if list.drop(1).empty? then
return list[0]
else
return f(list.drop(1))
end
end
 Write a recursive function to return the next to last element
of a list whose length is at least 2.
Answer
def f(list)
if list.drop(2).empty? then
return list[0]
else
return f(list.drop(1))
end
end
 Given an arbitrarily deeply nested list containing a number
at the bottom, such as [[[[47]]]], write a recursive function to
return the number.
Answer
def f(x)
if x.kind_of?(Array)
return f(x[0])
else
return x
end
end
 Write a recursive function to return the length of a list.
Answer
def f(list)
if list.empty?
return 0
else
return 1 + f(list.drop(1))
end
end
 Given an arbitrarily deeply nested list containing a number
at the bottom, such as [[[[47]]]], write a recursive function to
measure and return the depth.
Answer
def f(x)
if x.kind_of?(Array)
return 1 + f(x[0])
else
return 0
end
end
 Write a recursive function to_depth(n) that returns
nil buried in n levels of brackets, e.g., to_depth(4) should
return [[[[nil]]]].
Answer
def to_depth(n)
if n == 0
return nil
else
return [to_depth(n1)]
end
end
Recursion on Strings
When recursing on a string you cannot use the drop function, but you
can remove the first character from a string x by writing
x[1..1]. Also, writing x[0] will give you the
ASCII code for the first character of the string (a value between 0 and
255), but writing x[0..0] will give you the first character
as a string, e.g., "banana"[0] gives 98, but
"banana"[0..0] gives "b".
 Write a recursive function to print out the ASCII code for a
string as a sequence of numbers followed by spaces, e.g.,
f("banana") should print "98 97 110 97 110 97 ".
Answer
def f(x)
if not x.empty? then
print x[0], " "
f(x[1..1])
end
end
 Write a recursive function to compute the length of a string.
You may use the empty? method but not size or length.
Answer
def f(x)
if x.empty? then
return 0
else
return 1 + f(x[1..1])
end
end
 Write a recursive function to count the number of vowels in a string.
Answer
def f(x)
if x.empty? then
return 0
elsif ["a","e","i","o","u"].include?(x[0..0])
return 1 + f(x[1..1])
else
return f(x[1..1])
end
end
Recursion on Integers
 Write a recursive function f(n) to print the numbers n through 1 in descending order.
Answer
def f(n)
if n > 0 then
puts n
f(n1)
end
end
 Write a recursive function f(n) to print the numbers 1 through n in ascending order.
Answer
def f(n)
if n > 0 then
f(n1)
puts n
end
end
 Write the recursive version of the factorial function
fact(n) that returns the product 1 × 2 × ... × (n1) × n.
Answer
def f(n)
if n == 0 then
return 1
else
return n * f(n1)
end
end
 Write a recursive function num_digits(n) that returns
the number of digits in a positive integer n. Example:
num_digits(268) should return 3, while
num_digits(9175) should return 4. Hint: you can eliminate
the last digit of an integer by dividing it by 10.
Answer
def num_digits(n)
if n == 0 then
return 0
else
return 1 + num_digits(n/10)
end
end
 Write a recursive function to_bits(n) that converts a positive integer into
an array of bits. Example: to_bits(131) should return [1,0,0,0,0,0,1,1]. Recall
that you can obtain the loworder bit of a number by writing n%2, and you can shift
a number one bit to the right (which eliminates the loworder bit) by writing n/2.
Answer
def to_bits(n)
if n == 0 then
return []
else
return to_bits(n/2) + [n%2]
end
end
Recursion on Trees
 Write a recursive function max_depth that returns the
maximum depth of a binary tree.
Answer
def max_depth(tree)
if not tree.kind_of?(Array) then
return 0
else
left_depth = max_depth(tree[0])
right_depth = max_depth(tree[1])
return 1 + max(left_depth, right_depth)
end
end
 Write a recursive function print_leaves that prints all the
leaves in a binary tree, in order.
Answer
def print_leaves(tree)
if not tree.kind_of?(Array) then
puts tree
else
print_leaves(tree[0])
print_leaves(tree[1])
end
end
 Write a recursive function count_leaves that returns the
number of leaves (terminal nodes) in a binary tree. Example:
count_leaves([[0,0],0]) should return 3.
Answer
def count_leaves(tree)
if not tree.kind_of?(Array) then
return 1
else
return count_leaves(tree[0]) + count_leaves(tree[1])
end
end
 Write a recursive function sum_leaves that returns the
sum of all the leaves in a binary tree. Example:
sum_leaves([[3,1],6]) should return 10.
Answer
def sum_leaves(tree)
if not tree.kind_of?(Array) then
return tree
else
return sum_leaves(tree[0]) + sum_leaves(tree[1])
end
end
 Write a recursive function count_nonterminals that returns the
number of nonterminal nodes in a binary tree. Example:
count_nonterminals([[0,0],0]) should return 2.
Answer
def count_nonterminals(tree)
if not tree.kind_of?(Array) then
return 0
else
left_count = count_nonterminals(tree[0])
right_count = count_nonterminals(tree[1])
return 1 + left_count + right_count
end
end
 Write a recursive function tree_reverse that
reverses all the nodes of a binary tree. Example: tree_reverse([[5,6],[7,8]])
should return [[8,7],[6,5]].
Answer
def tree_reverse(tree)
if not tree.kind_of?(Array) then
return tree
else
return [tree_reverse(tree[1]), tree_reverse(tree[0])]
end
end
 Write a recursive function nest_right(list) that
turns a list into a rightnested binary tree. Example:
nest_right([1,2,3,4]) should return [1,[2,[3,4]]]
Answer
def nest_right(list)
if list.length <= 2 then
return list
else
return [list[0], nest_right(list.drop(1))]
end
end
 Write a recursive function nest_left(list) that
turns a list into a leftnested binary tree. Example:
nest_left([1,2,3,4]) should return [[[1,2],3],4]
Answer
def nest_left(list)
if list.length <= 2 then
return list
else
return [nest_left(list[0..2]), list[1]]
end
end
 Write a recursive function make_tree(list) that
constructs a balanced binary tree from the elements of list
by recursively dividing the list in half with each recursive call. Examples:
make_tree([5]) should return 5; make_tree([5,6])
should return [5,6]; make_tree([5,6,7]) should
return [[5,6],7]; make_tree([5,6,7,8]) should
return [[5,6],[7,8]].
Answer
def make_tree(list)
n = list.length1
if n == 0 then
return list[0]
else
left = make_tree(list[0..n/2])
right = make_tree(list[(n/2+1)..n])
return [left, right]
end
end
 Write a recursive function full_tree(n) that returns
a complete binary tree of depth n. All the terminal nodes should be
nil. Examples: full_tree(2) should return
[[nil,nil],[nil,nil]], while full_tree(3) should
return [[[nil,nil],[nil,nil]].[[nil,nil],[nil,nil]]]
Answer
def full_tree(n)
if n == 0 then
return nil
else
return [full_tree(n1), full_tree(n1)]
end
end
