Recursão

Definições recursivas

O fatorial

O fatorial de um natural $n$ é o produto dos naturais de 1 a $n$: $n! = 1 \cdot 2 \cdots n$, com a convenção $0! = 1$. As reticências dessa fórmula escondem um laço, e a aula Laços ensinou a escrevê-lo. Ora, a mesma definição admite outra forma, que não menciona nenhum laço: o fatorial de $n$ é $n$ vezes o fatorial de $n - 1$, e o de 0 é 1.

Esta é uma definição recursiva: define o fatorial de $n$ por meio do fatorial de um número menor. Não é circular, porque cada aplicação da segunda regra desce um degrau e a escada termina na primeira: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. As duas regras têm nome. A primeira é o caso base, que dá o resultado sem se referir a nada mais; a segunda é o caso recursivo, que reduz o problema a uma instância menor do mesmo problema.

C++ permite que uma função chame a si mesma, e com isso a definição se traduz quase palavra por palavra.

#include <print>​// Fatorial de n.// Pré-condição: 0 <= n <= 12 (a cota se justifica mais adiante).// Pós-condição: retorna n! = 1 · 2 · ... · n, com 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // caso base    }    return n * factorial(n - 1);    // caso recursivo}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

O contrato não é decorativo: com $n = -1$ o caso recursivo chamaria com $-2$, depois com $-3$, e nunca alcançaria o 0; e $13!$ não cabe em um int. Muitos textos introdutórios escrevem este fatorial com o caso base if (n == 0 || n == 1), redundante mas inofensivo, e sem dizer nada dos negativos nem do tamanho do resultado: seu código não termina com $n < 0$ e dá um resultado sem sentido a partir de $13!$. Ambos os defeitos serão examinados em sua seção.

Caso base e caso recursivo

Toda função recursiva tem um ou vários casos base, que se resolvem diretamente, e um ou vários casos recursivos, que chamam a mesma função com um argumento menor em algum sentido preciso e combinam o que ela retorna.

A potência $x^n$, com $n$ natural, define-se por $x^0 = 1$ e $x^n = x \cdot x^{n - 1}$: o tamanho é o expoente. A soma dos algarismos de um natural $n$ (a de 2026 é $2 + 0 + 2 + 6 = 10$) define-se assim: se $n < 10$, a soma é $n$, porque tem um só algarismo; se não, é a soma dos algarismos de $\lfloor n / 10 \rfloor$, que é $n$ sem seu último algarismo, mais esse último algarismo, $n \bmod 10$. Aqui o tamanho é o número de algarismos.

#include <print>​// x elevado a n.// Pré-condição: n >= 0.// Pós-condição: retorna x^n, com x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// Soma dos algarismos decimais de n.// Pré-condição: n >= 0.// Pós-condição: retorna a soma dos algarismos de n.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("soma dos algarismos de 2026: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375soma dos algarismos de 2026: 10

Escrever uma função recursiva consiste, portanto, em responder a duas perguntas: que casos se resolvem sem ajuda, e como se obtém a solução de um caso a partir da de um menor. Se ambas as respostas estão corretas, a função também está, e a seção seguinte o demonstra.