11.7 Advanced exercises

ds4psy: Exercises on Functions (11)

The following more advanced exercises cover some topics introduced as Advanced aspects (in Section 11.4).

11.7.1 Exercise A1

Recursive arithmetic

Define some arithmetic operation (e.g., computing the sum, product, etc., of a vector) as a recursive function.

11.7.2 Exercise A2

A rose is a rose…

Most illustrations of recursive functions address mathematical phenomena. As a non-numeric example, consider the literary phrase

“A rose is a rose is a rose is a rose.”

that is based on a poem by Gertrude Stein and became a popular meme (see flowery of the ds4psy package for 60 variants of the phrase). The appeal of the phrase is largely due to its recursive aspect — so we should be able to use recursion to program a generator function for it.

  1. Analysis:

    • What part of the phrase is recursive? Which one is not?
    • What is the stopping condition? What should happen when it is reached?

  1. Write a recursive function get_phrase(x = "rose", n = 3) that generates the phrase by repeating the part paste0("is a", x) n times.

    • Note: It’s easy to write a function using repetition, but try writing a truly recursive function.
    • Hint: Consider using an auxiliary function that only handles the recursive part of the phrase.

11.7.3 Exercise A3

Solving the Towers of Hanoi (ToH)

The video clip Recursion ‘Super Power’ (in Python) by Computerphile explains how to recursively solve the Towers of Hanoi problem in Python:

  1. Watch the video and then solve the problem for \(n\) discs (e.g., by writing a function ToH(n = 4)) in R.

  1. Use your ToH() function for solving the n = 3 case and answer the following questions:

    • How many disc moves does this require?

    • How often does the function meet the stopping criterion (i.e., n == 0)?
      Hint: To determine this, you could print out “ok” (or some counter value) every time you reach this condition.

  1. The solution shown in the video provides a recipe for solving the problem, but does not explicate which disc is being transferred on each move.
    Slightly adjust the move() helper function and its call in the ToH() function so that the disc being transferred is identified by its size n (with n = 1 denoting the smallest disc, and n = n denoting the largest disk).

11.7.4 Exercise A4

More sorting and measuring

  1. Watch the following video clip and implement at least one sorting algorithm not yet illustrated in this chapter as an R function.
  • 15 Sorting Algorithms in 6 Minutes (by Timo Bingmann): Visualization and “audibilization” of 15 sorting algorithms in 6 minutes. Sorts random shuffles of integers, with both speed and the number of items adapted to each algorithm’s complexity.
  1. Compare the performance of your new function with those discussed in Section 11.4.2 on a suitable range of problems.

11.7.5 Exercise A5

Vectorizing a function

The base2dec() function (from the ds4psy package) converts a sequence of numeral digits from some base notation into numerals in our familiar decimal notation (i.e., base = 10). Thus, the following numerals (1001 in base = 2, 101 in base = 3, etc.) all represent the same numeric value of \(10\):

library(ds4psy)

a <- base2dec(1010, base = 2)
b <- base2dec( 101, base = 3)
c <- base2dec(  22, base = 4)
d <- base2dec(  20, base = 5)

all.equal(a, b, c, d, 10)
#> [1] TRUE
  1. What happens when using the function with vector inputs?
base2dec(c(1, 10, 11, 100), base = 2)
  1. Create a vectorized version base2dec_vec() of the base2dec() function and use it to verify:
base2dec_vec(c(1, 10, 11, 100), base = 2)
#> [1] 1 2 3 4
  1. Predict and explain the result of the following expression:
base2dec_vec(x = c(1, 10, 11, 100), base = 2:3)

This concludes the more advanced exercises on programming in R.