Propriedades de algoritmos recursivos

Esta é a ideia básica por trás dos algoritmos recursivos:

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 $(n-1)!$‍ (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 $(-1)!$‍, você tentaria primeiro calcular $(-2)!$‍, para que você pudesse multiplicar o resultado por $-1$‍. Mas para calcular $(-2)!$‍, você tentaria primeiro computar $(-3)!$‍, para que você pudesse multiplicar o resultado por $-2$‍. E então você tentaria calcular $(-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!$‍. 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!=n\cdot (n-1)!$‍ e dividir ambos os lados por $n$‍, dando $n!/n=(n-1)!$‍. Vamos criar uma nova variável, $m$‍ e estipular que o seu valor seja igual a $n+1$‍. Já que nossa fórmula aplica-se a qualquer número positivo, vamos substituir $m$‍ por $n$‍, chegando a $m!/m=(m-1)!$‍. Já que $m=n+1$‍, nós agora temos $(n+1)!/(n+1)=(n+1-1)!$‍. Trocando de lado e notando que $n+1-1=n$‍ nos dá $n!=(n+1)!/(n+1)$‍. Esta fórmula nos leva a acreditar que você pode calcular $n!$‍ calculando primeiro $(n+1)!$‍ e, em seguida, dividindo o resultado por $n+1$‍. Mas para calcular $(n+1)!$‍, você teria que calcular $(n+2)!$‍, então $(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$‍ é positivo, você nunca atingiria o caso base de 0.

Podemos destilar a ideia de recursividade em duas regras simples:

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.