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:
If an array has no elements, it is an empty array;
Otherwise, the array is composed by one element followed by a slightly smaller array.
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:
If the array is empty, the number of elements is zero;
Otherwise, the number of elements is one plus the number of elements of the rest of the array
To ensure the correctness of our reasoning, we must guarantee that the requirements of a proper recursive definition are satisfied, namely:
There is a reduction of the problem’s complexity in every recursive invocation: in fact, in each recursive invocation the array becomes smaller;
There is a simplest case where the answer is immediate: when the array is empty, the number of elements is zero;
The result of the recursion is used to respond to the original problem: it is true that the number of elements in an array is the same as adding \(1\) to the number of elements in that array without the first element.
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