4.6. Blocos de Pilha: Implementando Recursão¶
Suponha que, em vez de concatenar o resultado da chamada recursiva
para toStr
com a string de convertString
, nós modificamos nosso
algoritmo para empilhar as strings antes de fazer a chamada recursiva.
O código para este algoritmo modificado é mostrado no
ActiveCode 1.
Cada vez que chamamos a função toStr
, colocamos um caractere na pilha.
Voltando ao exemplo anterior, podemos ver que após a quarta chamada
para toStr
a pilha ficaria como na Figura 5.
Note que agora podemos simplesmente desempilhar os caracteres e concatená-los
para formar o resultado final, "1010"
.

Figura 5: Strings Colocados na Pilha Durante a Conversão¶
O exemplo anterior nos dá uma ideia de como o Python implementa uma chamada de função recursiva. Quando uma função é chamada em Python, um bloco de pilha (stack frame) é alocado para cuidar das variáveis locais da função. Quando a função retorna, o bloco é desempilhado e o valor de retorno é deixado no topo da pilha de chamadas (call stack) para ser acessada pela função que fez a chamada. A Figura 6 ilustra a pilha de chamadas após o comando return na linha 4.

Figura 6: Pilha de Chamadas Gerada por toStr(10,2)
¶
Note que a chamada toStr(2//2,2)
deixa o valor de retorno
"1"
na pilha. Este valor de retorno é então usado no lugar da
chamada de função (toStr(1,2)
) na expressão "1" + convertString[2%2]
,
que irá deixar a string "10"
no topo da pilha.
Desta forma, a pilha de chamadas do Python toma o lugar da
pilha que usamos explicitamente na Listagem 4.
Em nosso exemplo de soma de números de uma lista,
você pode considerar que o valor de retorno na pilha substitui
a variável acumuladora.
O bloco de pilha também fornecem um escopo para as variáveis usadas pela função. Mesmo que estejamos chamando a mesma função repetidamente, cada chamada cria um novo escopo para as variáveis que são locais à função.