Propriedades de algoritmos recursivos

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

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 $(n-1)!$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!$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)!$left parenthesis, minus, 1, right parenthesis, !, você tentaria primeiro calcular $(-2)!$left parenthesis, minus, 2, right parenthesis, !, para que você pudesse multiplicar o resultado por $-1$minus, 1. Mas para calcular $(-2)!$left parenthesis, minus, 2, right parenthesis, !, você tentaria primeiro computar $(-3)!$left parenthesis, minus, 3, right parenthesis, !, para que você pudesse multiplicar o resultado por $-2$minus, 2. E então você tentaria calcular $(-4)!$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!$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 \cdot (n-1)!$n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! e dividir ambos os lados por $n$n, dando $n! / n = (n-1)!$n, !, slash, n, equals, left parenthesis, n, minus, 1, right parenthesis, !. Vamos criar uma nova variável, $m$m e estipular que o seu valor seja igual a $n+1$n, plus, 1. Já que nossa fórmula aplica-se a qualquer número positivo, vamos substituir $m$m por $n$n, chegando a $m! / m = (m-1)!$m, !, slash, m, equals, left parenthesis, m, minus, 1, right parenthesis, !. Já que $m = n + 1$m, equals, n, plus, 1, nós agora temos $(n+1)! / (n+1) = (n+1-1)!$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+1-1 = n$n, plus, 1, minus, 1, equals, n nos dá $n! = (n+1)! / (n+1)$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!$n, ! calculando primeiro $(n + 1)!$left parenthesis, n, plus, 1, right parenthesis, ! e, em seguida, dividindo o resultado por $n+1$n, plus, 1. Mas para calcular $(n+1)!$left parenthesis, n, plus, 1, right parenthesis, !, você teria que calcular $(n+2)!$left parenthesis, n, plus, 2, right parenthesis, !, então $(n + 3)!$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$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.