7.3 Modelo de Execução

mais simples que poderia ser apresentado e que deve ter uma solução trivial. Perceba que se o item 1 chama a função reduzindo a complexidade, a função deve convergir para esse caso trivial. No problema desta seção, saber o tamanho de uma lista vazia é o problema trivial.

EXERCÍCIO 7.1

Escreva uma função recursiva que imprima uma string na ordem inversa. Ex.:

“celacanto provoca maremoto” será impressa como “otomeram acovorp otnacalec”.

EXERCÍCIO 7.2

Escreva uma função recursiva que diga se uma palavra é um palíndromo. Ex: arara,

ovo, radar, osso.

EXERCÍCIO 7.3

Escreva uma função recursiva que diga se uma frase é um palíndromo. Não

esqueça de ignorar ou apagar os espaços antes de comparar as letras. Ex: “A mala

nada na lama”, “a base do teto desaba”.

Uma solução recursiva não tem laços de execução. A repetição

da ação se faz por meio de chamadas recursivas.

7.3 MODELO DE EXECUÇÃO

É instrutivo entender como Python funciona quando é feita uma chamada recursiva. Python tem uma estrutura chamada pilha em que são guardadas as informações das chamadas às funções. Independentemente de ser recursiva ou não, uma função tem que guardar seu estado e suas variáveis na pilha.

O que é a pilha? Uma pilha é uma estrutura que guarda informações de tal modo que você só tem acesso à última informação guardada. É como uma pilha de pratos. Ao final do almoço em família de domingo, alguém faz uma pilha de pratos, mas só pode lavar se começar pelo topo. Só se pode tirar um prato por vez, para não provocar um desastre, e uma vez esse prato retirado, é possível lavar/processar o próximo.

Figura 7.2 Pilha com “dois pratos”.

A pilha, nos computadores, é uma estrutura que serve para organizar o acesso às informações. Veja o exemplo recursivo de saber sua posição em uma fila. Você só pode saber sua resposta depois que cada um à sua frente processou a informação. Cada vez que você pergunta à pessoa à sua frente “qual é o seu lugar na fila?”, é como colocar uma informação na pilha, esperando a resposta. Quando o primeiro responde que é o número 1, esse elemento não é mais necessário e pode sair da pilha.

Mas o que se guarda na pilha? Python vai colocar na pilha, para cada chamada de função, os parâmetros da própria função e o endereço de retorno, quer dizer, o número da linha em que o programa estava executando quando foi chamado. Na verdade não é linha, mas o endereço de memória para retorno. Para simplificar as coisas, vamos pensar nesse endereço como a linha do programa.

A cada chamada, Python coloca informações sobre a função na pilha e trabalha com uma versão menor da lista da qual se está calculando o tamanho. Quando encontra uma resposta, no caso zero, salva o resultado na pilha e retorna ao fluxo principal do programa.

Vamos acompanhar a pilha para o programa de cálculo do

tamanho da lista.

Figura 7.3 Pilha inicial.

No início a pilha tem apenas a lista fila da função e uma

variável inteira, tamanho, ainda sem valor. Na primeira chamada a tam(), o programa coloca a variável f no topo da pilha e um espaço

para o valor a ser retornado para quem chamou (Figura 7.4).

Figura 7.4 Primeira chamada de tam().

Depois desta primeira chamada, a função tam() vai ser

chamada sucessivamente, cada vez com uma versão simplificada da lista. Toda vez que isso ocorre, uma nova posição é ocupada na pilha. A pilha vai crescer de acordo com o número de chamadas recursivas. Note que nada é resolvido, mas Python deixa espaço para que o programa volte pela pilha até o programa que chamou

originalmente tam() (Figura 7.5).

Quando as chamadas encontram uma função trivial, que dá uma

resposta, começa o processo de retorno de resultados e esvaziamento da pilha. A regra da pilha de que só pode ser retirada a função que está no topo, garante que a resposta irá seguir entre as funções até chegar à primeira função.

Perceba que cada nível da pilha guarda as variáveis da instância da função. Tudo funciona como se a cada chamada Python criasse uma cópia exata da função e desse novas variáveis para a função trabalhar. Não é feita uma cópia de tam() na realidade. Python simplesmente indica à mesma função quais são os dados com os quais vai trabalhar. Apesar do mesmo nome, as variáveis f de cada nível são entidades completamente independentes. A única forma de passar um valor de volta a quem chamou é por meio do comando return.

Figura 7.5 Chamadas a tam() e retorno.

Cada retorno diminui o tamanho da pilha. A memória ocupada

pelas variáveis de cada “cópia” de tam() é liberada (Figura 7.6).

Figura 7.6 Retornos diminuem o tamanho da pilha.

Esse processo continua até que a resposta chegue à função que

originou a primeira chamada (Figura 7.7).

Figura 7.7 Resultado final.

Edsger W. Dijkstra – 1930-2002.

Dijkstra (pronuncia-se déikstra) foi um dos mais importantes cientistas de computação

do século XX. Nascido na Holanda, cunhou o termo “Programação Estruturada” e

com seus textos sobre computação foi um dos precursores da engenharia de software,

possibilitando aos programadores organizar e gerenciar a complexidade crescente do

desenvolvimento de software.

Muitos dos conceitos desenvolvidos por Dijkstra são hoje parte das disciplinas da

Ciência da Computação. Dijkstra escrevia textos datilografados em que discutia

diversos aspectos da programação de computadores. Hoje esses textos estão

disponíveis gratuitamente on-line.