7.1 Fila de Programadores Míopes

Antes de apresentar a técnica com programas, gostaria de contar uma pequena história para ilustrar como a recursão pode resolver problemas. Depois a gente passa o conceito para o mundo dos computadores.

Após muitos anos trabalhando em frente ao computador sem

cuidar de seus olhos, você ficou bastante míope. Mas muito míope mesmo. Um dia, alguém lhe informa de que uma grande ótica está doando óculos de grau para programadores míopes. Oba! Esta é grande chance de voltar a enxergar bem! Você vai à loja, mas, quando chega lá, depara-se com uma fila gigante, dobrando o quarteirão. Como você não enxerga muito bem, não tem nenhuma ideia de quantas pessoas estão à sua frente. Mas é uma fila de programadores! Você pode usar a recursão para conhecer sua posição.

Figura 7.1 Fila de Programadores Míopes. Fonte: Leontura |

Stockphoto.com.

Como? Você sabe que sua posição será 1 mais a posição da

pessoa à sua frente. Você toca no ombro dela e pergunta:

– Qual a sua posição na fila?

Ela também não sabe, e pergunta à pessoa na frente:

– Qual a sua posição na fila?

E esse processo vai de pessoa a pessoa até chegar ao primeiro da fila que, não tendo ninguém à frente, sabe que é o primeiro. Ele responde:

– Sou o número 1.

O segundo, ao receber esta resposta, olha para trás e responde:

– Sou o número 2.

O seguinte olha para trás e responde:

– Sou o número 3.

E esse processo se repete pela fila até chegar a você. A pessoa que está à sua frente vai responder qual é a sua posição e você irá somar 1 para conhecer a sua própria posição.

Veja que, apesar da quase totalidade das pessoas que estão na fila não saberem de sua própria posição, você obteve uma resposta porque uma pessoa da fila sabia ser a primeira. A pergunta se propagou pela fila até chegar a ela, e cada pessoa por onde a pergunta passou só teve de acrescentar 1 ao número respondido pela pessoa que estava à frente.

A recursão é baseada na capacidade que uma função tem de chamar a si própria. Uma função sempre pode chamar outra função, mas o que acontece se esta chama a si própria? Se for feito sem controle, a função irá se chamar indefinidamente até travar o seu computador. Por isso, você precisa colocar algum bloqueio. Em algum ponto, a função recursiva deve parar de se chamar e retornar um resultado. No caso da fila de míopes era a pessoa que tinha certeza de sua posição, pois não tinha ninguém à frente de si para perguntar.

O que acontece é que uma função recursiva cada vez que chama a si mesma resolve uma versão mais simples do problema original. A pergunta feita na fila foi sempre a mesma, essa é nossa função.

A estrutura de base da solução é: