Conteúdo principal
Ciência da Computação
Curso: Ciência da Computação > Unidade 1
Lição 6: Algoritmos recursivos- Recursividade
- A função fatorial
- Desafio: Fatorial iterativo
- Fatorial recursivo
- Desafio: Fatorial recursivo
- Propriedades de algoritmos recursivos
- Usando recursividade para determinar se uma palavra é um palíndromo
- Desafio: A string é um palíndromo?
- Calculando a potência de um número
- Desafio: Potência recursiva
- Recursão múltipla com o triângulo de Sierpinski
- Melhorando a eficiência das funções recursivas
- Projeto: Arte recursiva
© 2023 Khan AcademyTermos de usoPolítica de privacidadeAviso de cookies
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:
- Cada chamada recursiva deve ser em uma instância menor do mesmo problema, ou seja, um subproblema menor.
- 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.