# 15-110 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

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

2. What value does print return?

Answer
print returns nil.

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

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

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

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

7. Fill in the blanks:

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

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

3. The _________ statement always produces output on the console.

Answer
print

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

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

1. ["a", "b", "c", "d"]
Answer
["a"] + x

2. ["b", "c", "d", "e"]
Answer
x + ["e"]

3. [["b", "c", "d"]]
Answer
[x]

4. ["a", ["b", "c", "d"]]
Answer
["a", x]

5. ["b", "c", "d", "b", "c", "d"]
Answer
x + x

6. [["b", "c", "d"], ["b", "c", "d"]]
Answer
[x,x]

7. ["b", "c", "d", ["b", "c", "d"]]
Answer
x + [x]

2. Given x = ["b", "c", "d"], write a short Ruby expression using collect to produce each of the following results:

1. [["a", "b"], ["a", "c"], ["a", "d"]]
Answer
x.collect {|e| ["a",e]}

2. ["bb", "cc", "dd"]
Answer
x.collect {|e| e+e}

3. [[["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:
1. 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 non-list 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.

2. How can I derive a smaller problem from this one? For numbers, this often means subtracting one from the input. For flat (non-nested) 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.

3. 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:

1. What should the base case be? ___________

Answer
n is 0.

2. Given an input n, how can you make a smaller problem from this one? _________________

Answer
Replace n by n-1.

3. 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(n-1)         ____
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 non-destructively 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

1. 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
f(list.drop(1))
end
end
```

2. 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
end
end
```

3. 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 + f(list.drop(1))
end
end
```

4. 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.odd? then
return list
else
return f(list.drop(1))
end
end
```

5. 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.odd? then
return [list] + f(list.drop(1))
else
return f(list.drop(1))
end
end
```

6. Write a recursive function to return the last element of a non-empty list. Note: you can do this non-recursively by writing list.last or list[-1] or list[list.length-1], but the idea here is to do it recursively.
Answer
```def f(list)
if list.drop(1).empty? then
return list
else
return f(list.drop(1))
end
end
```

7. 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
else
return f(list.drop(1))
end
end
```

8. Given an arbitrarily deeply nested list containing a number at the bottom, such as [[[]]], write a recursive function to return the number.
Answer
```def f(x)
if x.kind_of?(Array)
return f(x)
else
return x
end
end
```

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

10. Given an arbitrarily deeply nested list containing a number at the bottom, such as [[[]]], write a recursive function to measure and return the depth.
Answer
```def f(x)
if x.kind_of?(Array)
return 1 + f(x)
else
return 0
end
end
```

11. 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(n-1)]
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 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" gives 98, but "banana"[0..0] gives "b".

1. 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, " "
f(x[1..-1])
end
end
```

2. 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
```

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

1. 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(n-1)
end
end
```

2. 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(n-1)
puts n
end
end
```

3. Write the recursive version of the factorial function fact(n) that returns the product 1 × 2 × ... × (n-1) × n.
Answer
```def f(n)
if n == 0 then
return 1
else
return n * f(n-1)
end
end
```

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

5. 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 low-order bit of a number by writing n%2, and you can shift a number one bit to the right (which eliminates the low-order 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

1. 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)
right_depth = max_depth(tree)
return 1 + max(left_depth, right_depth)
end
end
```

2. 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)
print_leaves(tree)
end
end
```

3. 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) + count_leaves(tree)
end
end
```

4. 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) + sum_leaves(tree)
end
end
```

5. 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)
right_count = count_nonterminals(tree)
return 1 + left_count + right_count
end
end
```

6. 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), tree_reverse(tree)]
end
end
```

7. Write a recursive function nest_right(list) that turns a list into a right-nested 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, nest_right(list.drop(1))]
end
end
```

8. Write a recursive function nest_left(list) that turns a list into a left-nested 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
```

9. 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() 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.length-1
if n == 0 then
return list
else
left = make_tree(list[0..n/2])
right = make_tree(list[(n/2+1)..n])
return [left, right]
end
end
```

10. 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(n-1), full_tree(n-1)]
end
end
```

Dave Touretzky
Last modified: Sat Feb 2 02:48:47 EST 2013