PHP Recursão

Uma função recursiva é uma função que chama a si mesma. Parece um truque de mágica (ou um jeito de travar o computador), mas é a forma mais natural de resolver problemas que têm "coisas dentro de coisas": pastas dentro de pastas, menus com submenus, comentários com respostas. Nesta aula você vai entender como isso funciona por dentro, quando usar e o que acontece quando dá errado.

Antes, você precisa saber criar uma função com parâmetros e return (aula Funções) e percorrer um array com foreach. Os exemplos rodam na máquina da Ana, dentro da pasta ~/site.

A ideia antes do código: a fila do cinema

A Ana está numa fila enorme de cinema e quer saber em que posição está. Ela não consegue ver o começo da fila. Então ela pergunta para a pessoa da frente: "Em que posição você está?". Essa pessoa também não sabe, e faz a mesma pergunta para quem está na frente dela. E assim por diante…

…até chegar na primeira pessoa da fila. Ela não precisa perguntar a ninguém: responde "estou na posição 1". A resposta volta: quem estava atrás dela responde "então eu sou a 2", o próximo diz "3"… até a resposta chegar na Ana.

Repare nas duas partes dessa história. Toda recursão tem exatamente essas duas:

Se faltar o caso base, a pergunta nunca para. Se o problema não diminuir, nunca se chega ao caso base. Os dois erros terminam do mesmo jeito, como você vai ver no fim da aula.

Primeira recursão: contagem regressiva

Vamos começar pelo exemplo mais simples possível: contar de 3 até 1 e dizer "Fogo!".

<?php
function contagem(int $n): void
{
    if ($n === 0) {
        echo "Fogo!\n";
        return;
    }
    echo $n, "\n";
    contagem($n - 1);
}

contagem(3);

$ php contagem.php
3
2
1
Fogo!

O que aconteceu, chamada por chamada:

1. contagem(3): 3 não é 0, escreve 3 e chama contagem(2).
2. contagem(2): escreve 2 e chama contagem(1).
3. contagem(1): escreve 1 e chama contagem(0).
4. contagem(0): é o caso base. Escreve Fogo! e volta. Como não há mais nada depois das chamadas, todas terminam.

A ida e a volta: a pilha de chamadas

Esse "cada chamada espera a próxima terminar" tem nome: pilha de chamadas (call stack). Pense numa pilha de pratos: cada chamada nova é um prato colocado em cima; quando uma chamada termina, o prato de cima sai, e quem estava embaixo continua de onde parou.

Fica fácil de ver se colocarmos um echo depois da chamada recursiva:

<?php
function idaEVolta(int $n): void
{
    if ($n === 0) {
        echo "chegou ao fundo\n";
        return;
    }
    echo "descendo: $n\n";
    idaEVolta($n - 1);
    echo "subindo: $n\n";
}

idaEVolta(3);

$ php ida-e-volta.php
descendo: 3
descendo: 2
descendo: 1
chegou ao fundo
subindo: 1          « a chamada com $n = 1 continua depois que a de baixo terminou
subindo: 2
subindo: 3          « a primeira chamada é a última a terminar

A linha echo "subindo: $n\n" de cada chamada só roda quando a chamada de baixo termina. Por isso os números voltam ao contrário: 1, 2, 3. E repare que cada chamada se lembra do próprio $n, como dissemos.

<?php
function idaEVolta(int $n): void
{
    if ($n === 0) {
        echo "chegou ao fundo\n";
        return;
    }
    echo "descendo: $n\n";
    idaEVolta($n - 1);
    echo "subindo: $n\n";
}

idaEVolta(3);

Uma recursão que devolve valor: o fatorial

O fatorial de um número (escrito com !) é a multiplicação dele por todos os inteiros menores até 1. Ele aparece em matemática para contar combinações: de quantas formas a Ana pode arrumar 5 livros na estante? 5! = 5 × 4 × 3 × 2 × 1 = 120.

Repare num detalhe: 5 × 4 × 3 × 2 × 1 é o mesmo que 5 × (4 × 3 × 2 × 1), ou seja, 5 × 4!. O fatorial de 5 é 5 vezes o fatorial de 4. Isso é um problema definido por uma versão menor dele mesmo, o lugar perfeito para recursão:

<?php
function fatorial(int $n): int
{
    if ($n <= 1) {
        return 1;
    }
    return $n * fatorial($n - 1);
}

echo fatorial(5), "\n";
for ($i = 0; $i <= 6; $i++) {
    echo "$i! = ", fatorial($i), "\n";
}
echo fatorial(20), "\n";

function fatorial(int $n): int

Recebe um inteiro e devolve um inteiro.

if ($n <= 1) { return 1; }

Caso base. Usamos <= 1 (e não === 1) para que fatorial(0) também pare aqui.

return $n * fatorial($n - 1);

Passo recursivo: para calcular a multiplicação, o PHP precisa primeiro do resultado de fatorial($n - 1). Ele chama a função, espera a resposta, multiplica por $n e devolve.

$ php fatorial.php
120
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
2432902008176640000          « 20!, já um número enorme

Seguindo o fatorial(4) de perto

Na ida, cada chamada fica esperando. Na volta, cada uma recebe a resposta de baixo, faz a sua multiplicação e passa o resultado para cima:

Leia a coluna "na volta" de baixo para cima: 1, 2, 6, 24. É a mesma fila do cinema, com multiplicação no lugar da soma.

<?php
function fatorial(int $n): int
{
    if ($n === 0) {
        return 0;
    }
    return $n * fatorial($n - 1);
}

echo "4! = ", fatorial(4), "\n";
echo "5! = ", fatorial(5), "\n";

<?php
function fatorial(int $n): int
{
    if ($n === 0) {
        return 1;
    }
    return $n * fatorial($n - 1);
}

echo "4! = ", fatorial(4), "\n";
echo "5! = ", fatorial(5), "\n";

Por que dava zero? O caso base devolvia 0, e qualquer número multiplicado por zero é zero. O valor do caso base "contamina" todas as voltas: escolher o valor certo nele é tão importante quanto ter um.

Onde a recursão brilha: árvores

Contagem e fatorial são bons para aprender, mas, na prática, um for resolve os dois (você vai ver isso daqui a pouco). A recursão fica insubstituível quando os dados têm uma forma de árvore: um item que tem itens dentro, que têm itens dentro… sem você saber quantos níveis existem.

Um menu com submenus

A Ana quer um menu para o site de receitas. Algumas seções têm subseções, que podem ter subseções também. Em PHP, isso é um array associativo em que cada valor é outro array (os filhos), vazio quando não há filhos:

<?php
$menu = [
    "Início"   => [],
    "Receitas" => [
        "Doces"    => [
            "Bolos"  => [],
            "Tortas" => [],
        ],
        "Salgados" => [],
    ],
    "Contato"  => [],
];

function mostrarMenu(array $itens, int $nivel = 0): void
{
    foreach ($itens as $nome => $filhos) {
        echo str_repeat("    ", $nivel), "- ", $nome, "\n";
        mostrarMenu($filhos, $nivel + 1);
    }
}

mostrarMenu($menu);

array $itens, int $nivel = 0

A função recebe um pedaço do menu e o nível de profundidade, que começa em 0 se ninguém disser nada (valor padrão; veja Parâmetros).

foreach ($itens as $nome => $filhos)

Para cada item deste nível: $nome é o texto ("Receitas") e $filhos é o array de dentro.

str_repeat(" ", $nivel)

Repete 4 espaços $nivel vezes: é o recuo que mostra a profundidade.

mostrarMenu($filhos, $nivel + 1)

Passo recursivo: "mostre os filhos deste item, um nível mais para dentro". O problema diminui porque $filhos é um pedaço menor da árvore.

$ php menu.php
- Início
- Receitas
    - Doces
        - Bolos
        - Tortas
    - Salgados
- Contato

Onde está o caso base? Ele está escondido: quando um item não tem filhos, $filhos é [] e o foreach de um array vazio não faz nenhuma volta. A função termina sem chamar mais ninguém. Todo array vazio é uma "folha" da árvore.

O mais bonito: se a Ana acrescentar "Brigadeiros" => [] dentro de "Bolos", a função continua funcionando sem mudar uma vírgula. Ela não sabe quantos níveis existem, nem precisa.

O mesmo menu numa página web

No site, o menu vira listas HTML (<ul>) dentro de listas. A função agora devolve o HTML como texto em vez de escrevê-lo. Repare no htmlspecialchars: o nome de cada item vai para o HTML protegido, como deve ser com todo texto que vira página (veja Escapar a Saída).

<?php
$menu = [
    "Início"   => [],
    "Receitas" => [
        "Doces"    => [
            "Bolos"  => [],
            "Tortas" => [],
        ],
        "Salgados" => [],
    ],
    "Contato"  => [],
];

function menuHtml(array $itens): string
{
    if ($itens === []) {
        return "";
    }
    $html = "<ul>\n";
    foreach ($itens as $nome => $filhos) {
        $html .= "<li>" . htmlspecialchars($nome) . menuHtml($filhos) . "</li>\n";
    }
    return $html . "</ul>\n";
}
?>
<!doctype html>
<html lang="pt-BR">
<head><meta charset="utf-8"><title>Receitas da Ana</title></head>
<body>
<h1>Receitas da Ana</h1>
<?= menuHtml($menu) ?>
</body>
</html>

<?php
$menu = [
    "Início"   => [],
    "Receitas" => [
        "Doces"    => [
            "Bolos"  => [],
            "Tortas" => [],
            "Pudins" => [],
        ],
        "Salgados" => [],
    ],
    "Contato"  => [],
];

function menuHtml(array $itens): string
{
    if ($itens === []) {
        return "";
    }
    $html = "<ul>\n";
    foreach ($itens as $nome => $filhos) {
        $html .= "<li>" . htmlspecialchars($nome) . menuHtml($filhos) . "</li>\n";
    }
    return $html . "</ul>\n";
}
?>
<!doctype html>
<html lang="pt-BR">
<head><meta charset="utf-8"><title>Receitas da Ana</title></head>
<body>
<h1>Receitas da Ana</h1>
<?= menuHtml($menu) ?>
</body>
</html>

Aqui o caso base é explícito: if ($itens === []) return "";. Sem ele, todo item sem filhos ganharia um <ul></ul> vazio no HTML. O código-fonte gerado pelo exemplo (antes da missão) é este; note como cada <ul> de dentro fica no meio de um <li>:

$ php menu-web.php
<!doctype html>
<html lang="pt-BR">
<head><meta charset="utf-8"><title>Receitas da Ana</title></head>
<body>
<h1>Receitas da Ana</h1>
<ul>
<li>Início</li>
<li>Receitas<ul>
<li>Doces<ul>
<li>Bolos</li>
<li>Tortas</li>
</ul>
</li>
<li>Salgados</li>
</ul>
</li>
<li>Contato</li>
</ul>
</body>
</html>

As pastas da Ana: somar o que está dentro

Agora uma árvore em que a função precisa juntar respostas. A Ana representou as pastas do computador assim: um arquivo é nome => tamanho em bytes; uma pasta é nome => [o que tem dentro]. Quanto espaço tudo ocupa?

<?php
// nome do arquivo => tamanho em bytes; nome da pasta => [o que tem dentro]
$casa = [
    "frutas.txt" => 47,
    "Documentos" => [
        "notas.txt"  => 69,
        "alunos.csv" => 180,
        "projetos"   => [
            "site" => [
                "index.php" => 340,
                "ola.php"   => 26,
            ],
        ],
    ],
    "Música" => [],
];

function tamanhoTotal(array $pasta): int
{
    $total = 0;
    foreach ($pasta as $nome => $conteudo) {
        if (is_array($conteudo)) {
            $total += tamanhoTotal($conteudo);   // é uma pasta: pergunte a ela
        } else {
            $total += $conteudo;                 // é um arquivo: some o tamanho
        }
    }
    return $total;
}

echo "Tudo junto: ", tamanhoTotal($casa), " bytes\n";
echo "Só Documentos: ", tamanhoTotal($casa["Documentos"]), " bytes\n";

$ php pastas.php
Tudo junto: 662 bytes
Só Documentos: 615 bytes

Confira de cabeça: site = 340 + 26 = 366; projetos = 366; Documentos = 69 + 180 + 366 = 615; tudo = 47 + 615 + 0 (a pasta Música está vazia) = 662. Cada pasta responde só por si e pergunta às de dentro, exatamente como as pessoas da fila.

Recursão × laço

Tudo o que se faz com recursão dá para fazer com um laço, e vice-versa. O fatorial com um for fica assim:

<?php
function fatorial(int $n): int
{
    $resultado = 1;
    for ($i = 2; $i <= $n; $i++) {
        $resultado *= $i;
    }
    return $resultado;
}

echo fatorial(5), "\n";

$ php fatorial-laco.php
120

Mesmo resultado. Então, qual usar? Há uma diferença prática importante: cada chamada que fica esperando na pilha ocupa memória. Um laço de um milhão de voltas usa a mesma memória do começo ao fim; uma recursão de um milhão de níveis guarda um milhão de chamadas ao mesmo tempo. Veja a soma de 1 até n feita com recursão:

<?php
function somarAte(int $n): int
{
    if ($n === 0) {
        return 0;
    }
    return $n + somarAte($n - 1);
}

echo somarAte(100), "\n";
echo somarAte(100000), "\n";
echo somarAte(1000000), "\n";

$ php somar.php | head -4
5050
5000050000

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 262144 bytes) in /home/ana/site/somar.php on line 7

Cem mil níveis funcionaram; um milhão, não: a memória que o PHP pode usar (128 MB, o padrão do memory_limit) acabou antes. O | head -4 está ali porque, depois dessa linha, o PHP 8.5 mostra o caminho de todas as chamadas que estavam na pilha, mais de 700 mil linhas (mais sobre isso em Quando dá errado). Com um laço, o mesmo cálculo para um milhão não tem problema nenhum.

Quando dá errado

<?php
function contagem(int $n): void
{
    echo $n, "\n";
    contagem($n - 1);
}

contagem(3);

$ php infinita.php > saida.txt
$ echo $?
255                              « 255 = o PHP terminou com erro fatal
$ grep -A4 "Fatal" saida.txt
Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 262144 bytes) in /home/ana/site/infinita.php on line 5
Stack trace:
#0 /home/ana/site/infinita.php(5): contagem(-915005)
#1 /home/ana/site/infinita.php(5): contagem(-915004)
#2 /home/ana/site/infinita.php(5): contagem(-915003)
$ tail -3 saida.txt
#915007 /home/ana/site/infinita.php(5): contagem(2)
#915008 /home/ana/site/infinita.php(8): contagem(3)
#915009 {main}
$ wc -l saida.txt
1830022 saida.txt                « quase 2 milhões de linhas!

<?php
function fatorial(int $n): int
{
    if ($n === 0) {
        return 1;
    }
    return $n * fatorial($n - 1);
}

echo fatorial(-1), "\n";

$ php negativo.php | head -3

Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 262144 bytes) in /home/ana/site/negativo.php on line 7
Stack trace:

<?php
function fatorial(int $n): int
{
    if ($n <= 1) {
        return 1;
    }
    $n * fatorial($n - 1);
}

echo fatorial(5), "\n";

$ php sem-return.php

Fatal error: Uncaught TypeError: fatorial(): Return value must be of type int, none returned in /home/ana/site/sem-return.php:8
Stack trace:
#0 /home/ana/site/sem-return.php(7): fatorial(2)
#1 /home/ana/site/sem-return.php(7): fatorial(3)
#2 /home/ana/site/sem-return.php(7): fatorial(4)
#3 /home/ana/site/sem-return.php(10): fatorial(5)
#4 {main}
  thrown in /home/ana/site/sem-return.php on line 8

<?php
$casa = [
    "frutas.txt" => 47,
    "Documentos" => [
        "notas.txt"  => 69,
        "alunos.csv" => 180,
    ],
];

function tamanhoTotal(array $pasta): int
{
    $total = 0;
    foreach ($pasta as $nome => $conteudo) {
        if (is_array($conteudo)) {
            tamanhoTotal($conteudo);
        } else {
            $total += $conteudo;
        }
    }
    return $total;
}

echo tamanhoTotal($casa), " bytes\n";

$ php esqueceu-somar.php
47 bytes                 « deveria ser 296: os arquivos de Documentos sumiram

$ php fatorial.php       « o mesmo fatorial.php, com echo fatorial(21) no fim
…
2432902008176640000

Fatal error: Uncaught TypeError: fatorial(): Return value must be of type int, float returned in /home/ana/site/fatorial.php:7
Stack trace:
#0 /home/ana/site/fatorial.php(15): fatorial(21)
#1 {main}
  thrown in /home/ana/site/fatorial.php on line 7

Referência

Exercícios

Missão final

<?php
$casa = [
    "frutas.txt" => 47,
    "Documentos" => [
        "notas.txt"  => 69,
        "alunos.csv" => 180,
        "projetos"   => [
            "site" => [
                "index.php" => 340,
                "ola.php"   => 26,
            ],
        ],
    ],
    "Música" => [
        "forro.mp3" => 4100000,
    ],
];

function contarArquivos(array $pasta): int
{
    $quantos = 0;
    foreach ($pasta as $conteudo) {
        // complete aqui
    }
    return $quantos;
}

echo "A Ana tem ", contarArquivos($casa), " arquivos.\n";

<?php
$casa = [
    "frutas.txt" => 47,
    "Documentos" => [
        "notas.txt"  => 69,
        "alunos.csv" => 180,
        "projetos"   => [
            "site" => [
                "index.php" => 340,
                "ola.php"   => 26,
            ],
        ],
    ],
    "Música" => [
        "forro.mp3" => 4100000,
    ],
];

function contarArquivos(array $pasta): int
{
    $quantos = 0;
    foreach ($pasta as $conteudo) {
        if (is_array($conteudo)) {
            $quantos += contarArquivos($conteudo);
        } else {
            $quantos++;
        }
    }
    return $quantos;
}

echo "A Ana tem ", contarArquivos($casa), " arquivos.\n";

Resumo

• Uma função recursiva chama a si mesma. Ela precisa de um caso base (responde sem se chamar) e de um passo recursivo (se chama com um problema menor).
• Cada chamada tem as suas próprias variáveis. As chamadas ficam empilhadas esperando; o código depois da chamada recursiva roda "na volta", em ordem contrária.
• Numa recursão que devolve valor, use a resposta da chamada: return $n * fatorial($n - 1);, $total += tamanhoTotal($sub);.
• A recursão brilha em árvores: menus, pastas, categorias, comentários com respostas. Para contar e repetir, prefira um laço.
• Sem caso base (ou com um caso base inalcançável), o PHP esgota a memória: Fatal error: Allowed memory size of … bytes exhausted, seguido de um stack trace com a mesma função repetida.