In a previous post I introduced the return stack facility for Bash. Now I present an example of how to implement recursion using this facility:
#!/bin/bash
############################################################
# Example script to demonstrate recursion without the
# use of subshells
#
# John Robertson <john@rrci.com>
# Initial release: Thu Sep 10 11:58:23 EDT 2020
#
# Halt on error, no globbing, no unbound variables
set -efu
# import return stack tools
source ../bash++
# "static" array of phrases to be assembled into
# a sentence by recurse()
declare -a Phrase_arr=(\
[0]='Now is' \
[1]='the time for' \
[2]='all good' \
[3]='men to come' \
[4]='to the aide of' \
[5]='their country'\
)
# Convenient "constant"
Phrase_arr_sz=${#Phrase_arr[@]}
function recurse ()
#######################################################
# Example recursive function works without subshells
# Arguments:
# Recursion level
# Returns:
# contcatenated phrases
#
{
local lvl=$1
# Continue recursing until out of phrases
if (( lvl + 1 < Phrase_arr_sz )); then
# Call ourself again with incremented lvl
recurse $(( lvl + 1 ))
# Pop the result into R1
RTN_pop R1
# Push concatenated result on return stack
RTN_push "${Phrase_arr[$lvl]} $R1"
else
# Push final phrase on return stack
RTN_push "${Phrase_arr[$lvl]}"
fi
}
###################################
### Execution starts here #########
###################################
# NOTE: We'll reserve R1 R2 R3 ... global
# variables to fetch return values from
# return stack.
# Recursively assemble sentence from Phrase_arr
recurse 0
# Retrieve sentence from return stack
RTN_pop R1
# Print result
echo "Result: '$R1'"
... and the result is:
Result: 'Now is the time for all good men to come to the aide of their country'
All files referenced here are available on Github!
Top comments (0)