If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Propriedades de algoritmos recursivos

Esta é a ideia básica por trás dos algoritmos recursivos:
Para solucionar um problema, solucione um subproblema que seja uma instância menor do mesmo problema, e então use a solução dessa instância menor para solucionar o problema original.
Quando calculamos n, !, solucionamos o problema de calcular n, ! (o problema original) solucionando o subproblema de calcular o fatorial de um número menor, ou seja, calculando left parenthesis, n, minus, 1, right parenthesis, ! (a instância menor do mesmo problema), e então usando a solução do subproblema para calcular o valor de n, !.
Para um algoritmo recursivo funcionar, os problemas menores devem em algum momento chegar ao caso base. Quando calculamos n, !, os subproblemas ficam cada vez menores até que calculamos 0, !. Você precisa ter a certeza de chegar até o problema base.
Por exemplo, e se nós tentássemos calcular o fatorial de um número negativo, usando nosso método recursivo? Para calcular left parenthesis, minus, 1, right parenthesis, !, você tentaria primeiro calcular left parenthesis, minus, 2, right parenthesis, !, para que você pudesse multiplicar o resultado por minus, 1. Mas para calcular left parenthesis, minus, 2, right parenthesis, !, você tentaria primeiro computar left parenthesis, minus, 3, right parenthesis, !, para que você pudesse multiplicar o resultado por minus, 2. E então você tentaria calcular left parenthesis, minus, 4, right parenthesis, !, e assim por diante. Claro, os números estão ficando cada vez menores, mas eles também estão cada vez mais distantes do caso base que é calcular 0, !. Você nunca conseguiria obter uma resposta.
Mesmo se você puder garantir que o valor de n não seja negativo, ainda poderá ter problemas se você não fizer os subproblemas progressivamente menores. Aqui está um exemplo. Vamos pegar a fórmula n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! e dividir ambos os lados por n, dando n, !, slash, n, equals, left parenthesis, n, minus, 1, right parenthesis, !. Vamos criar uma nova variável, m e estipular que o seu valor seja igual a n, plus, 1. Já que nossa fórmula aplica-se a qualquer número positivo, vamos substituir m por n, chegando a m, !, slash, m, equals, left parenthesis, m, minus, 1, right parenthesis, !. Já que m, equals, n, plus, 1, nós agora temos left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis, equals, left parenthesis, n, plus, 1, minus, 1, right parenthesis, !. Trocando de lado e notando que n, plus, 1, minus, 1, equals, n nos dá n, !, equals, left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis. Esta fórmula nos leva a acreditar que você pode calcular n, ! calculando primeiro left parenthesis, n, plus, 1, right parenthesis, ! e, em seguida, dividindo o resultado por n, plus, 1. Mas para calcular left parenthesis, n, plus, 1, right parenthesis, !, você teria que calcular left parenthesis, n, plus, 2, right parenthesis, !, então left parenthesis, n, plus, 3, right parenthesis, !, e assim por diante. Você nunca chegaria no caso base de 0. Por que não? Porque cada subproblema recursivo pede para calcular o valor de um número maior, não um número menor. Se n é positivo, você nunca atingiria o caso base de 0.
Podemos destilar a ideia de recursividade em duas regras simples:
  1. Cada chamada recursiva deve ser em uma instância menor do mesmo problema, ou seja, um subproblema menor.
  2. As chamadas recursivas precisam em algum ponto alcançar um caso base, que é resolvido sem outra recursão.
Vamos voltar às bonecas russas. Embora elas não figurem em quaisquer algoritmos, vê-se que cada boneca engloba todas as bonecas menores (análogo ao caso recursivo), até a boneca menor que não engloba nenhuma outra (como no caso base).

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

Nenhuma postagem por enquanto.
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.