Recursividade
Última atualização
Recursão é uma função que chama a si mesma sobre uma versão menor do mesmo problema, até chegar a um caso tão pequeno que pode ser respondido diretamente. Esse caso que se responde diretamente é o caso base, e toda função recursiva precisa de um: fib(n) continua se dividindo em fib(n - 1) e fib(n - 2) até chegar a fib(1) ou fib(0), que simplesmente retornam a si mesmos. O visualizador acima faz exatamente isso: aperte reproduzir e veja as chamadas se ramificarem em uma árvore, alcançarem os casos base nas folhas e então devolverem seus valores de volta para cima, combinando-se em cada nível.
A segunda coisa que a animação mostra é a pilha de chamadas: toda chamada que começou mas ainda não retornou. A pilha cresce conforme as chamadas ficam mais profundas, atinge o pico na profundidade da recursão e se desfaz à medida que os resultados voltam, e é por isso que uma recursão profunda pode causar um estouro de pilha enquanto um laço iterativo nunca faz a pilha crescer. O mesmo formato de chamadas está no coração da busca em profundidade, do merge sort e da maioria das operações sobre uma árvore binária.
Complexidade de tempo e espaço
Para o Fibonacci recursivo ingênuo mostrado acima, e as duas correções padrão:
| Abordagem | Tempo | Espaço | Notas |
|---|---|---|---|
| Recursão ingênua | O(2^n) | O(n) | A árvore de chamadas dobra a cada nível; o espaço é a pilha mais profunda, não a árvore inteira. |
| Com memoização | O(n) | O(n) | Cada fib(k) é calculado uma única vez e fica em cache; as subárvores repetidas viram simples consultas. |
| Laço iterativo | O(n) | O(1) | Duas variáveis rotativas substituem a pilha por completo. |
| Qualquer recursão, em geral | chamadas × trabalho por chamada | O(max depth) | A pilha guarda um quadro por chamada que começou e ainda não retornou. |
Passo a passo
| Passo | O que acontece |
|---|---|
| 1 | A primeira chamada fib(n) entra na pilha de chamadas. |
| 2 | Ela precisa de fib(n - 1), então essa chamada também entra na pilha; a chamada pai espera. |
| 3 | As chamadas continuam se aninhando até uma delas perguntar por n <= 1: o caso base responde na hora, sem nenhuma chamada mais profunda. |
| 4 | O valor do caso base retorna para a chamada pai, que agora pode iniciar sua segunda chamada, fib(n - 2). |
| 5 | Quando as duas chamadas filhas retornam, o pai soma os valores e retorna também; seu quadro sai da pilha. |
| 6 | O retorno se repete subindo pela árvore até que o quadro da primeira chamada sai com a resposta final e a pilha fica vazia. |
Exemplo resolvido
Avaliando fib(4) na ordem exata das chamadas, como a animação reproduz:
| Chamada | Pilha naquele momento | Retorna |
|---|---|---|
fib(4) | fib(4) | espera pelas filhas |
fib(3) | fib(4) > fib(3) | espera pelas filhas |
fib(2) | fib(4) > fib(3) > fib(2) | espera pelas filhas |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (caso base) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (caso base) |
fib(2) combina | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (caso base) |
fib(3) combina | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) de novo | fib(4) > fib(2) | 1, recalculado do zero |
fib(4) combina | fib(4) | 2 + 1 = 3 |
Quando usar recursão
| Use quando | Evite quando |
|---|---|
| O problema é autossimilar: árvores, estruturas aninhadas, divisão e conquista | Um laço simples expressa a mesma coisa sem quadros de pilha |
A profundidade é limitada e modesta, como O(log n) no merge sort | A profundidade pode chegar ao tamanho da entrada em entradas enormes, arriscando um estouro de pilha |
| O backtracking precisa da pilha para lembrar onde retomar | Os mesmos subproblemas se repetem e você não está guardando os resultados em cache |
| A versão recursiva é claramente mais fácil de ler e de verificar | Você está em um laço crítico onde o custo de cada chamada pesa de verdade |
Código de Recursion
Uma implementação limpa e executável de Recursion em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Recursion em Python
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Código de Recursion em JavaScript
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Código de Recursion em Java
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Código de Recursion em C++
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Código de Recursion em C
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}Perguntas frequentes sobre recursão
O que é um caso base na recursão?
É a entrada pequena o bastante para ser respondida sem outra chamada recursiva. Para
fib(n) é n <= 1, que retorna n diretamente. Sem um caso base alcançável, as chamadas nunca param, a pilha continua crescendo e o programa quebra com um estouro de pilha.O que é a pilha de chamadas e por que ela importa?
O ambiente de execução mantém um quadro por chamada que começou mas ainda não retornou, guardando seus argumentos e suas variáveis locais. A profundidade da recursão é igual à altura da pilha, então uma recursão que desce
n níveis usa O(n) de memória mesmo que cada chamada quase não faça trabalho. A linha de fichas abaixo da animação mostra exatamente essa pilha crescendo e se desfazendo.Por que o Fibonacci recursivo leva tempo exponencial?
Porque os mesmos subproblemas são recalculados várias e várias vezes: no exemplo resolvido acima,
fib(2) é avaliado duas vezes dentro de fib(4), e a duplicação praticamente dobra a cada nível, resultando em O(2^n) chamadas. Guardar cada resultado em cache na primeira vez em que ele é calculado, o que se chama memoização, reduz a árvore para O(n).Recursão é melhor que iteração?
Nenhuma das duas é melhor em todos os casos. Toda recursão pode ser reescrita como um laço com uma pilha explícita, e todo laço como uma recursão. A recursão ganha em legibilidade para problemas autossimilares, como a travessia de árvores e a busca em profundidade; a iteração ganha em memória e em custo de chamada para percursos lineares.
O que causa um estouro de pilha em uma função recursiva?
Ou um caso base ausente ou inalcançável, fazendo com que as chamadas nunca parem, ou uma recursão correta cuja profundidade é simplesmente grande demais para o limite de pilha do ambiente de execução, como recorrer uma vez por elemento em uma entrada de milhões. As correções são garantir o caso base, limitar a profundidade ou converter para iteração.
Quais algoritmos são naturalmente recursivos?
Ordenações de divisão e conquista como o merge sort e o quicksort, travessias de uma árvore binária e de grafos, busca binária, quebra-cabeças de backtracking como as N rainhas, e tudo que é definido sobre uma estrutura aninhada, como JSON ou um sistema de arquivos.
Recursos relacionados
Mais visualizações
