On this page:
6.2.1 Exercises 29
6.2.1.1 Question 88
6.2.1.2 Question 89
6.2.1.3 Question 90
6.2.1.4 Question 91
6.2.1.5 Question 92
6.2.1.6 Question 93

6.2 Recursion over Arrays

It should be clear that an array slice is still an array. This fact provides an interesting point of view over arrays: they are a recursive data type. If we slice an array, we obtain a smaller version of the same array. This is visible in the example below:

> students = ["John", "Peter", "Mary"]

3-element Vector{String}:

 "John"

 "Peter"

 "Mary"

> students[2:end]

2-element Vector{String}:

 "Peter"

 "Mary"

This means we can decompose an array into its first element and its remaining elements:

> students == [students[1], students[2:end]...]

true

This also means that we can successively reduce an array by computing its slice from the second element to the end, until we get an empty array:

> students = students[2:end]

2-element Vector{String}:

 "Peter"

 "Mary"

> students = students[2:end]

1-element Vector{String}:

 "Mary"

> students = students[2:end]

String[]

This means that an array can be described by a recursive definition, where the array concept is described in terms of itself:

Notice that, in the previous definition, the stopping condition is the empty array.

One of the interesting properties of recursive types is that operations that deal with elements of recursive type can be implemented by recursive functions. For example, to define a function that tells us how many elements an array has, we can think recursively:

To ensure the correctness of our reasoning, we must guarantee that the requirements of a proper recursive definition are satisfied, namely:

Translating the previous recursive definition into Julia, we get the following function:

number_of_elements(array) = array == [] ? 0 : 1+number_of_elements(array[2:end])

Here are two examples of the use of the function:

> number_of_elements([1, 2, 3, 4])

4

> number_of_elements([])

0

It is important to note that the presence of subarrays is irrelevant for the computation of the number of elements in an array: each subarray is just an element of the array and, thus, counts as one. For example:

> number_of_elements([[1, 2], [3, 4, 5, 6]])

2

As we can see in the previous example, the array only contains two elements, despite each element being an array with more elements.

Despite formally correct, the recursive algorithm to compute the number of elements of an array is not efficient, as it depends on the creation of a series of increasingly smaller arrays. To address this problem, Julia provides the predefined function length that does the same as the function number_of_elements in a much more efficient way. An example of its use is shown below:

> length([1, 2, 3, 4])

4

6.2.1 Exercises 29
6.2.1.1 Question 88

Define a delete_nth function that receives a number \(n\) and an array, and deletes the \(n\)th element of the array.

Consider the following example of the function usage:

> delete_nth(2, [1, 2, 3, 4, 5])

4-element Vector{Int64}:

 1

 3

 4

 5

6.2.1.2 Question 89

Write a function that, given an array, returns a randomly selected element of that array.

6.2.1.3 Question 90

Define the one_of_each function that, given an array of arrays, creates an array containing a random element of each array, in the same order. For example:

> one_of_each([[0, 1, 2], [3, 4], [5, 6, 7, 8]])

3-element Vector{Int64}:

 1

 3

 7

> one_of_each([[0, 1, 2], [3, 4], [5, 6, 7, 8]])

3-element Vector{Int64}:

 1

 4

 8

> one_of_each([[0, 1, 2], [3, 4], [5, 6, 7, 8]])

3-element Vector{Int64}:

 2

 3

 5

6.2.1.4 Question 91

Define the random_elements function that, given a number \(n\) and an array, returns \(n\) elements of the array picked randomly. For example:

> random_elements(3, [0, 1, 2, 3, 4, 5, 6])

3-element Vector{Int64}:

 0

 1

 6

6.2.1.5 Question 92

Define the reversed function that, given an array, returns an array containing the same elements but in reverse order.

6.2.1.6 Question 93

Given that arrays are flexible data structures, we often use arrays containing other arrays that, in turn, may contain other arrays, and so on. That is the case, for example, of the arrays [[1, 2], [3, 4]] and [[[1, 2], [3, 4], [5, 6]], [[7, 8], [9, 0]]]

Write a function called flatten that receives an array as argument, possibly containing other arrays, and returns another array with all the elements of the original array, in the same order, but without any subarrays, for example:

> flatten([1, 2, [3, 4, [5, 6]], 7])

7-element Vector{Int64}:

 1

 2

 3

 4

 5

 6

 7