16 Recursion

Placeholder for chapter under construction.

Links to Slides

Quarto Presentations that I sometimes use in class:

Glossary

TODO

Exercises

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

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"

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!
```
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

15 Object-Oriented Programming in R

References