Os shells suportam recursão?

Question

Estou tentando escrever funções recursivas em meus scripts de shell. Considere o seguinte código:

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) 

O código falha:

• 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: "

No entanto, em parte sucede usando ksh88 . Apenas a segunda função falha:

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

• Estou fazendo algo errado?
• Existe outra sintaxe recursiva suportada por bash e zsh?
• Por que a segunda função ( factorial ) falha em ksh ?

PS : Eu sei, a recursão é mal, tem um desempenho ruim, eu deveria usar um loop regular em vez disso, bla bla bla. Não estou discutindo se a recursão é boa ou ruim, mas se os shells comuns a suportam. Eu não sou tolo o suficiente para enviar funções recursivas em produção quando simples loops iterativos funcionariam:)

    

Answer 1

• Erro de sintaxe: não use citações dentro da avaliação aritmética.
• Erro de lógica: você está misturando os valores STDOUT e return .

Transmitir valores como STDOUT:

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

factorial 5

Ou return deles:

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

factorial 5
echo $?

Ambos os códigos funcionam em bash , ksh (93 certo, nenhuma ideia sobre 88) e zsh , então eu acho que sim, os shells suportam recursão.

    

Answer 2

A recursão não é má; contanto que você esteja ciente do que acontece internamente quando você chama uma função e as armadilhas.

Primeiro, verifique se você tem uma condição de parada que será executada quando a função recursiva concluir sua tarefa. Se você não fizer isso, você não terá uma função recursiva, mas um loop indiferente.

Em seguida, variáveis e pontos de reentrada. Cada chamada para uma função envia informações na pilha; o endereço do ponto de reentrada (endereço da próxima instrução quando a função retorna). Então você tem que reservar o espaço para o tipo de valor de retorno tg.

Em seguida, é uma questão de escopo. As variáveis passam como parâmetros e as variáveis locais são declaradas na função. Cada vez que a função é chamada, esse espaço tem que ser alocado na pilha e é mantido lá até ser exibido retornando à função de chamada. Então, eventualmente, você ficará sem memória de pilha (condição de estouro de pilha).

Eu escrevi um programa de "Torres de Hanói" para uma aula de pascal que estava sendo ensinada em um DEC Vax. Eu tentei criar uma condição que iria travar meu programa ou VMS por ser capaz de adicionar tantos pólos e quantos anéis eu quisesse. Cheguei a 1000 toques em 3 poles e o programa ainda funcionava. Demorou cerca de 10 minutos para correr, mas correu.

De qualquer forma, voltemos à sua pergunta. O que parece estar acontecendo aqui é que suas variáveis estão no escopo errado - parece que elas estão sendo invocadas no ambiente global, não no local. Assim, quaisquer alterações feitas na variável pela função são refletidas em todas as instâncias da função. Todas as alterações precisam ser feitas em um escopo local e, em seguida, os valores retornados para a função de chamada. Não tenho certeza se uma linguagem interpitiva como o bash suporta variáveis locais e pode tornar todas as variáveis visíveis para toda a lógica do script.

Espero que isso ajude.