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 :)

Solution

• 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.

Comments

[rahmu]

It worked on ksh88

[l0b0]

You really don't want to return numerical values which could be higher than 255. Use STDOUT.

[grochmal]

It isn't a bad discussion about recursion but (1) OPs problem was really with the quoted syntax and (2) this has been consistently answered 4 years ago

[Chris]

I just found it while searching google, I didn't pay attention to the date.