# 16 Recursion

Placeholder for chapter under construction.

TODO

## Exercises

1. Write a recursive function called is_palindrome() that, when given any vector, returns TRUE if the vector is the same as itself reversed, and returns FALSE otherwise. The function should take a single parameter called vec, the vector to check for being a palindrome.

Typical examples of use should be as follows:

## vectors of length 0 are palindromes:
is_palindrome(vec = character())
## [1] TRUE
is_palindrome(vec = "x")
## [1] TRUE
is_palindrome(vec = c(2, 2))
## [1] TRUE
is_palindrome(vec = c("b", "a", "b", "a"))
## [1] FALSE
2. Write a recursive function called substrings() that, when given any non-empty string, returns a character vector of the substrings of that string. The function should take a single parameter called str, the strings for which the substrings are found.

A typical example of use would be as follows:

## convenience function to order the
## elements of a character vector:
strings_ordered <- function(strs) {
data.frame(
strings = strs
) %>%
mutate(num_char = str_length(strings)) %>%
arrange(num_char, strings) %>%
pull(strings)
}

"yowsa" %>%
substrings() %>%
strings_ordered()
##  [1] "a"     "o"     "s"     "w"     "y"     "ow"    "sa"    "ws"
##  [9] "yo"    "ows"   "wsa"   "yow"   "owsa"  "yows"  "yowsa"
3. Write a recursive function called countup() will count up from a starting number to a finishing number. The function should take two parameters:

• start: the number at which to begin;
• n: the number at which to finish.

Typical examples of use should be as follows:

countup(start = 7, n = 6)
## start should not exceed n
countup(start = 6, n = 6)
## 6, ...
## All done!
countup(start = 1, n = 5)
## 1, ...
## 2, ...
## 3, ...
## 4, ...
## 5, ...
## All done!
4. In a weighted directed acyclic graph (WDAG), let us define a maximal subpath to be a path that begins at the root node and has a sum of node-values that is as large as possible. (Note that such a path need not continue all the way to a leaf.)

For example. consider the following WDAG:

wdag <- make_val_tree(
min_children = 1,
max_children = 3,
values = -5:5,
min_depth = 3,
seed = 5556
)

A maximal subpath for our WDAG is shown below (node fill for the path is burlywood):

Write a function called max_subpath() that, when given any WDAG, will return the sum of the weights of the nodes for its maximal subpath(s). The function should take a single parameter called node, whose value would be a WDAG as constructed using data.tree in class.

Here is what we get when we apply such a function to our example WDAG:

max_subpath(node = wdag)
## [1] 6