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! n! , solucionamos o problema de calcular n! n! (o problema original) solucionando o subproblema de calcular o fatorial de um número menor, ou seja, calculando (n1)! (n-1)! (a instância menor do mesmo problema), e então usando a solução do subproblema para calcular o valor de n! n! .
Para um algoritmo recursivo funcionar, os problemas menores devem em algum momento chegar ao caso base. Quando calculamos n! n! , os subproblemas ficam cada vez menores até que calculamos 0! 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 (1)! (-1)! , você tentaria primeiro calcular (2)! (-2)! , para que você pudesse multiplicar o resultado por 1 -1 . Mas para calcular (2)! (-2)! , você tentaria primeiro computar (3)! (-3)! , para que você pudesse multiplicar o resultado por 2 -2 . E então você tentaria calcular (4)! (-4)! , 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! 0! . Você nunca conseguiria obter uma resposta.
Mesmo se você puder garantir que o valor de n 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!=n(n1)! n! = n \cdot (n-1)! e dividir ambos os lados por n n , dando n!/n=(n1)! n! / n = (n-1)! . Vamos criar uma nova variável, m m e estipular que o seu valor seja igual a n+1 n+1 . Já que nossa fórmula aplica-se a qualquer número positivo, vamos substituir m m por n n , chegando a m!/m=(m1)! m! / m = (m-1)! . Já que m=n+1 m = n + 1 , nós agora temos (n+1)!/(n+1)=(n+11)! (n+1)! / (n+1) = (n+1-1)! . Trocando de lado e notando que n+11=n n+1-1 = n nos dá n!=(n+1)!/(n+1) n! = (n+1)! / (n+1) . Esta fórmula nos leva a acreditar que você pode calcular n! n! calculando primeiro (n+1)!(n + 1)! e, em seguida, dividindo o resultado por n+1 n+1 . Mas para calcular (n+1)! (n+1)! , você teria que calcular (n+2)! (n+2)! , então (n+3)! (n + 3)! , 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 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.
Carregando