Do shells support recursion?

Question

I'm trying to write recursive functions in my shell scripts. Consider the following code:

function printA {
    if [[ "$1" = 0 ]]; then
        return
    else
        echo "a$(printA $(("$1" - 1)))"
    fi
}
printA 10
function factorial {
if [[ "$1" = 0 ]]; then
    return 1
else
    return $(( "$1" * $(factorial $(( $1 - 1 )) ) ))
fi

}
echo $(factorial 5)

The code fails on:

• bash (3.0)

recur.sh: line 5: "10" - 1: syntax error: operand expected (error token is ""10" - 1")

a

recur.sh: line 16: "1" * : syntax error: operand expected (error token is ""1" * ")

recur.sh: line 16: "2" * : syntax error: operand expected (error token is ""2" * ")

recur.sh: line 16: "3" * : syntax error: operand expected (error token is ""3" * ")

recur.sh: line 16: "4" * : syntax error: operand expected (error token is ""4" * ")

recur.sh: line 16: "5" * : syntax error: operand expected (error token is ""5" * ")

• zsh (4.2.1)

printA:1: bad math expression: illegal character: "

a

factorial:5: bad math expression: illegal character: "

However it partly succeds using ksh88. Only the second function fails:

aaaaaaaaa

recur.sh[5]: 1 * : more tokens expected

recur.sh[5]: 2 * : more tokens expected

recur.sh[5]: 3 * : more tokens expected

recur.sh[5]: 4 * : more tokens expected

recur.sh[5]: 5 * : more tokens expected

• Am I doing anything wrong?
• Is there another recursive syntax supported by bash and zsh?
• Why does the second function (factorial) fail in ksh?

PS: I know, recursion is Evil, performs badly, I should use a regular loop instead, bla bla bla. I am not discussing whether recursion is good or bad, but whether common shells support it. I am not foolish enough to send recursive functions in production when simple iterative loops would do the trick :)

Answer 1

• Syntax error: use no quotes inside arithmetic evaluation.
• Logic error: you are mixing STDOUT and return values.

Either pass values as STDOUT:

function factorial {
    (( $1 )) &&
    echo $(( $1 * $( factorial $(( $1 - 1 )) ) )) ||
    echo 1
}

factorial 5

Or return them:

function factorial {
    (( $1 )) || return 1
    factorial $(( $1 - 1 ))
    return $(( $1 * $? ))
}

factorial 5
echo $?

Both codes work in bash, ksh (93 sure, no idea about 88) and zsh, so I guess yes, shells do support recursion.

Answer 2

Recursion is not evil; as long as you are aware of what happens internally when you call a function, and the pitfalls.

First, make sure tou have a stop condition that will execute when the recursive function completes its task. If you don't you don't have a recursive function, but an wndless loop.

Next, variables and re-entry points. Each call to a function pushes information on the stack; the address of the reentry point (address of the next instruction when the function returns). Then you have to reserve the space for tge return value type.

Next is a matter of scope. The variables passes as parameters, and the local variables declared in the function. Each time the function is called, this space has to be allocated on the stack, and is held there until popped out by returning to the calling function. So, eventually you will run out of stack memory (stack overflow condition).

I wrote a "Towers of Hanoi" program for a pascal class that was being taught on a DEC Vax. I tried to create a condition that would crash my program or VMS by being able to add as many poles and as many rings as I wanted. I got to 1000 rings on 3 poles, and the program still ran. It took about 10 minutes to run, but ir ran.

Anyway, back to your question. What seems to be going on here is your variables are in the wrong scope - it looks like they are being invoked in the global environment, not the local. So, any changes made in the variable by the function is reflected in all instances of the function. All changes need to be made in a local scope, and then the values returned to the calling function. I'm not sure if an interpitive language like bash supports local variables, and may make every variable visable to all the script's logic.