15-110 Ruby Drills

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

Thinking Recursively

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.

>> f(8)
********
=> nil

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.

def print_asterisks(n)
  if n == 0 then                 ____
    print "\n"
  else
    print "*"                    ____
    print_asterisks(n-1)         ____
end

Breaking A 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

puts x.first + " pie"

puts x.drop(1).first + " pie"

puts x.drop(1).drop(1).first + " pie"
puts x.drop(1).drop(1).drop(1).first + " pie"

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

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

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

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

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 [[[[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
    

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

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[0], " "
       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