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.