Recursividade §

---

Uma função ou procedimento recursivo é um tipo especial de módulo que contém sua descrição uma chamada para si mesmo (recursão).

A recursividade permite resolver um problema a partir de uma instância conhecida do problema, e as soluções para outras instâncias são conhecidas a partir desta.

Note

Em termos matemáticos, a recursão pode ser expressa e comprovada por meio da Indução Matemática no qual a instância conhecida representa a base indutiva e as próximas instâncias podem ser induzidas a por meio do passo indutivo.

Dessa foma, um problema “maior” é reduzido em problemas “menores” até que se consiga resolver.

De forma geral, para resolver um problema dessa natureza, podemos utilizar a seguinte estratégia.

se a entrada do problema é pequena então
	resolva-a diretamente;
senão,
	reduza-a a uma entrada menor do mesmo problema;
	aplique este método à entrada menor (chamada recursiva);
	use o retorno da função para calcular o resultado da
	solução completa.

Um dos exemplos mais famosos para demostrar um problema que pode ser resolvido de forma recursiva é o fatorial.

Cálculo do Fatorial §

O cálculo do fatorial de um número n, denotado como n!, é um dos exemplos clássicos de problemas que podem ser resolvidos tanto de forma iterativa quanto recursiva.

Fatorial Iterativo §

Primeiro, vejamos o cálculo do fatorial de forma iterativa. O algoritmo percorre todos os números de n até 1, multiplicando-os para obter o fatorial.

int fatorial(int n) {
    int r = 1;
    for (int i = n; i >= 1; i--)
        r = r * i;
    return r;
}

Nesse algoritmo:

• Inicializamos r como 1.
• Multiplicamos r por cada valor de i, que decrementa de n até 1.
• Ao final do loop, r contém o valor de n!.

Este é um exemplo de um algoritmo iterativo, onde um processo é repetido até que uma condição seja satisfeita (nesse caso, até que i seja 0).

Fatorial Recursivo §

Agora, vamos explorar a versão recursiva do cálculo do fatorial. A definição matemática de n! pode ser expressa recursivamente como:

Essa definição se traduz diretamente em código:

int fatorial(int n) {
    if (n == 0)
        return 1;
    else
        return n * fatorial(n - 1);
}

Caso Base: A função verifica se n é igual a 0. Se for, retorna 1, pois 0! = 1. Este é o caso base da recursão, que evita chamadas infinitas.

Warning

Todo algoritmo recursivo deve implementar o caso base, ter uma condição de parada, para evitar loops infinitos.

Passo Recursivo: Se n for maior que 0, a função retorna n multiplicado pelo fatorial de n - 1. Isso reduz o problema original (n!) a um problema menor ((n-1)!).

Para ilustrar a execução da função recursiva, considere a chamada fatorial(4):

Portanto, fatorial(4) resulta em 24.

Note

A profundidade da recursão é o número de chamadas recursivas de uma função.

Exemplo:

• fatorial(4) tem profundidade igual a 4.
• fatorial(10) tem profundidade igual a 10.

Referências §

---

https://drive.google.com/file/d/1vGZYPPw7PZuMMqXpjjUkF_kMGTmVv1-r/view?usp=drive_link