Compreendendo Recursão

Muito bem, semestre começou com tudo e estou aprendendo muita coisa nova! Uma delas que estou vendo agora é Recursão. Se você já ouvi falar de Algoritmos, provavelmente já deve ter ouvido falar de Recursão também. De acordo com o material da nossa aula

um processo recursivo é um processo que implementa uma relação de recorrência. Uma relação de recorrência é uma expressão matemática utilizada para expressar uma equação de recorrência.

Wait, what? Vamos por partes, pois esse é um conceito muito difícil de ser compreendido, mas vale a pena, prometo. O mais legal de se aprender recursão é criar algoritmos menores e mais bonitos (embora nem sempre seja o mais eficiente!). Resumindo, uma função recursiva vai chamar a si mesma e retornando os valores de cada chamada, até chegar no caso base.

Calma, não é mágica! Acredito que uma das maiores dificuldades seja compreender os passos para escrever uma função recursiva para que esta não caia num loop infinito. Por isso é preciso ter atenção às duas partes essenciais de uma chamada deste tipo e verificar com números inteiros o problema até que você entenda o que será o caso base e a chamada recursiva a partir do exemplo a seguir:

Considere um vetor de inteiros de tamanho n. Uma função recursiva que calcule o produto dos elementos estritamente positivos de um vetor de inteiros v [0..n-1].

 int produto (int v[], int n) {
     if(n == 1){
   	 return v[0];
     }
     if(v[n-1] > 0){
   	 return v[n-1] * produto(v, n-1);
    }
	return produto(v,n-1);
 }

O caso base – Essa é a parte que você sabe o resultado e deve se aproximar na próxima etapa. No exemplo abaixo, vemos que o caso base é a condição if (n == 1) return v[0];, pois quando o vetor chegar até o primeiro elemento, não há mais necessidade de se calcular o produto, certo?

A chamada recursiva – Esta deve ser quebrada em pedaços menores até atingir o caso base. No nosso exemplo, fazemos duas chamadas distintas. Caso o elemento da posição v[n-1] a ser testada seja positiva, então retornamos return v[n-1] * produto(v, n-1); , caso contrário, chamamos a função para continuar a descrescer o valor de n até atingir o valor de 1, nosso caso base.

O que a função faz é o seguinte. Vamos supor que o nosso vetor v[4] = {1, 2, 3, 4} e o tamanho do vetor seja n = 4.

produto(v, 4)

v[3] * produto(v, 3)
v[3] * v[2] * produto(v, 2)
v[3] * v[2] * v[1] * produto(v, 1)
v[3] * v[2] * v[1] * v[0]
>> 4 * 3 * 2 * 1 = 24

Esse exemplo foi retirado desse material e está disponívelneste link. Veja também outras formas de usar a recursividade para resolver o mesmo problema (:

Vá fazendo com calma cada passo para não se perder (o que é muito fácil) e compreender como o computador entende essas chamadas (vale printar todas as entradas para ver o valor de retorno a cada chamada). Dá um trabalho e sua cabeça buga por um momento (ou dias xD), mas seu código fica mais bonito e te deixa com uma sensação maravilhosa de finalmente aprender Recursão 🙂