0

RECURSIVIDADE – TUDO QUE VAI, VOLTA!

Márcio Morais
Márcio Morais

Segundo a lenda, Teseu, um herói ateniense foi até a ilha de Creta para matar o terrível Minotauro. O monstro vivia em um Labirinto, então Ariadne sua amada, deu-lhe um novelo de lã. Ela ficaria à entrada do palácio, segurando o novelo que Teseu iria desenrolando à medida que fosse avançando pelo labirinto. Para voltar ao ponto de partida, teria apenas que seguir novamente o fio. Teseu avançou, matou o monstro e conseguiu retornar.


A genialidade de demarcar um caminho, seja com migalhas de pão ou laços para depois voltar, desde então se tornou parte de grandes histórias. Apontar para uma direção segura, é um dos modos mais inteligentes de se resolver um problema, principalmente quando estamos falando de problemas computacionais.


Toda instrução de um programa ao ser executada, aponta para uma próxima instrução, e se uma mesma instrução se repetir, ou seja, chamar a si própria por muitas vezes, teremos na verdade a criação de uma pilha de instruções que facilmente poderá ser desempilhada.


O fato é que hoje nas linguagens mais modernas não programamos mais instrução por instrução, mas sim criamos blocos de códigos com comandos que serão responsáveis pela execução dessas instruções. Buscando abstrair essa ideia em um bloco, é possível que um bloco consiga invocar a si próprio até que uma determinada situação seja atendida.


Se um programa segue um curso em toda sua execução, e nessa execução em um ponto p um bloco invoque a si próprio por n vezes, será preciso que ao parar de recorrer, ele volte “pelo caminho” até o ponto p, para que o programa seja terminado. Repetir um caminho (curso) por algumas vezes e voltar (recurso) é o que chamamos na programação de recursividade.


Sendo assim, temos a seguinte definição:


Em ciência da computação, a recursividade é a definição de uma sub-rotina (função ou método) que pode invocar a si mesma.


O jeito simples de entender a recursividade é que, para entender a recursão, a pessoa deve primeiro entender a recursão [sic].


Brincadeiras à parte, vamos ver como isso funciona na prática com o mais simples dos algoritmos recursivos, o da Fatorial.


O fatorial de um número inteiro e positivo n, representado por n! é obtido a partir da multiplicação de todos os seus antecessores até o número um, cuja expressão genérica é n! = n . (n – 1). (n – 2). (n – 3)... 2,1.


Pela definição dada, o fatorial de 5 corresponde a 5! (lê-se cinco fatorial), sendo assim:


5! = 5 • 4 • 3 • 2 • 1 = 120.


Para desenvolver esse algoritmo vou utilizar a linguagem Javascript.



O código acima apresenta três variáveis (num, resp e n) e uma função (fatorial).


A função fatorial recebe o número cinco (5), e dentro dessa função há uma condição, que verifica se o número em n (5) é maior que um (1), o resultado dessa condição é verdadeiro, então a função fatorial é chamada novamente na linha abaixo:


return n * fatorial(n-1);


Nenhum cálculo é realizado, pois nesse momento é preciso esperar pelo retorno.


A fatorial de quatro (n-1) então é iniciada, e como parte desse bloco envolve a condição do valor de n (4) ser maior que um (1), a função fatorial novamente é chamada.


Esse bloco vai se repetindo, e a função fatorial é chamada enquanto a condição não for atendida, ou seja, n não for um (1).



Quando finalmente ocorre o fatorial (1), esse valor um (1) retorna para a última vez que a função fatorial foi chamada.


return n * fatorial(n-1);


ou seja,


return n * 1;


Quando a última fatorial foi chamada, o valor de n era dois (2). Se substituirmos as variáveis por seus respectivos valores teremos:


return 2 * 1;


O resultado dessa expressão então volta como retorno para a chamada anterior, como n valia 3, temos os seguintes valores:


return 3 * 2;


O valor 6 é retornado então para a chamada anterior:


return 4 * 6;


E por último com n contendo cinco (5), é calculada a seguinte expressão:


return 5 * 24;


Com a recursividade concluída, o valor é atribuído a variável resp.


Alguns conceitos importantes são necessários para entender a recursividade, dentre eles a precedência (ou prioridade) e operadores e a associatividade e o operador de atribuição.


A precedência controla a ordem em que os operadores da expressão são avaliados.


Em relação a associatividade, praticamente em todas as linguagens de programação os operadores retornam um valor com base nos seus operandos. O operador de atribuição = não é diferente. Ele aceita dois operandos: o operando à direita é avaliado e então é armazenado no operando à esquerda.


Vamos analisar a expressão abaixo:


return n * fatorial(n-1);


Antes de haver o retorno, é preciso que a fatorial seja calculada, depois multiplicada por n. Somente assim o retorno ocorrerá. Como a fatorial terá seu primeiro retorno apenas quando o valor de n for um (1), havendo fatorial(1) haverá o retorno de um (1) que será multiplicado então por dois (2) e em seguida o valor dois (2) será retornado para a chamada anterior. Sucessivamente.

0
0

Comentários (1)

2
Jean Nascimento

Jean Nascimento

03/04/2021 20:00

Artigo muito interessante, parabéns!

None

Brasil