Bash Arrays 5: Local Arrays in Recursive Functions

When making a bash recursive function we have to pay special attention to local variables. One special case is when we wish to pass an array to a recursive function.

When making recursive function, we have to be careful how we use variables. This post will deal with passing arrays as parameters to recursive functions.

Pre-requistites

1. Knowing how to declare an array and set its elements
2. Knowing how to get the indices of an array
3. Knowing how to cycle through an array
4. Knowing how to copy an array
5. Knowing how to pass arrays as parameters
6. Knowing how to make recursive function
7. Understand indirect expansion

Setup

Let’s make a shell script. In your favourite editor type

#!/bin/bash

And save it somewhere as recurse.sh. Now we need to make it executable as follows:

[ahmed@amayem ~]$ chmod +x ./recurse.sh 
[ahmed@amayem ~]$ ./recurse.sh 

Looks good so far.

Making a basic recursive function

declare -a letters=(a b c d)

recurse()
{
    local x=$1
    if [ $1 -lt 5 ]
    then
        recurse $(($1 + 1))
        echo $x
    fi
}

recurse 1

This should produce the following:

[ahmed@amayem ~]$ ./recurse.sh 
4
3
2
1

Simple Example

As we’ve seen in the previous post about passing arrays as paramaters we can pass arrays as names and use indirect expansion to obtain the contents of the array. What happens when the function is in a recursive call and the local variable is being initialized using the array of the same name? For example the following:

declare -a letters=(a b c d)

recurse()
{
    local x=$1 name=$2"[@]"
    local -a letters=(${!name})
    letters[$x]=$x
    echo ${letters[@]}
    if [ $1 -lt 5 ]
    then
        recurse $(($1 + 1)) letters
        echo ${letters[@]}
    fi
}

recurse 1 letters

This is the interesting part: local -a letters=(${!name}). Because the name variable here is actually letters[@], which means that the statement is: local -a letters=(${letters[@]}). Will it initialize properly? Let’s run it and see:

[ahmed@amayem ~]$ ./recurse.sh
a 1 c d
a 1 2 d
a 1 2 3
a 1 2 3 4
a 1 2 3 4 5
a 1 2 3 4
a 1 2 3
a 1 2 d
a 1 c d

Looks like it worked, and the changes we made to the local array did not affect the previous iteration’s local array.

Comprehensive example, works for sparse arrays

As discussed in the previous post about passing arrays as paramaters to be comprehensive we should copy the array with it’s proper indices.

Problematic first attempt

Let’s build on our first example and simply add the code that copies a sparse array properly as follows:

recurse()
{
    local x=$1
    local -a 'arraykeys=("${!'"$2"'[@]}")' letters

    arraykeysString=${arraykeys[*]}
    for index in $arraykeysString;
    do
        current=$2"[$index]"
        letters[$index]=${!current}
    done
    echo ${letters[@]} #$arraykeysString
    letters[(2*$x)]=$x
    if [ $1 -lt 5 ]
    then
        recurse $(($1 + 1)) letters
    fi
}

recurse 1 letters
echo done

This produces the following:

[ahmed@amayem ~]$ ./recurse.sh 





done

We get a bunch of empty lines. Upon further inspection we see the problem is in the following line: letters[$index]=${!current}, which would translate into letters[$index]=${letters[$index]}, which of course makes no sense. The previous simple example worked because the assignment was at the same time as the declaration, so bash was smart enough to use the letters of the calling function instead of the newly declared letters. To fix this we need to save the elements temporarily to a variable and use that variable to access the elements instead:

Functional Comprehensive Example

declare -a letters=(a b c d)

recurse()
{
    local x=$1 name=$2"[@]"
    local -a 'arraykeys=("${!'"$2"'[@]}")' 'lettersElements=(${!name})' letters

    for ((i=0; i<${#lettersElements[*]}; i++));
    do
        letters[${arraykeys[$i]}]=${lettersElements[$i]}
    done
    echo ${letters[@]} "|" ${!letters[@]}
    letters[(2*$x)]=$x
    if [ $1 -lt 5 ]
    then
        recurse $(($1 + 1)) letters
    fi
    echo ${letters[@]} "|" ${!letters[@]}
}

recurse 1 letters
echo done

lettersElements acted as the copy of the elements of the original letters array. We had to change the for loop method to one that uses numbers so that we can match each index/key in arrayKeys to the corresponding element in lettersElements. The result is as follows:

[ahmed@amayem ~]$ ./recurse.sh 
a b c d | 0 1 2 3
a b 1 d | 0 1 2 3
a b 1 d 2 | 0 1 2 3 4
a b 1 d 2 3 | 0 1 2 3 4 6
a b 1 d 2 3 4 | 0 1 2 3 4 6 8
a b 1 d 2 3 4 5 | 0 1 2 3 4 6 8 10
a b 1 d 2 3 4 | 0 1 2 3 4 6 8
a b 1 d 2 3 | 0 1 2 3 4 6
a b 1 d 2 | 0 1 2 3 4
a b 1 d | 0 1 2 3
done

Looks like the array and its indices are maintained. We have success.

References

1. All prerequisites