- Recursividade é uma forma interessante de resolver problemas. Essa forma se aplica quando um problema pode ser dividido em problemas menores (subproblemas) de mesma natureza que o problema original.
- Como os subproblemas têm a mesma natureza do problema original, o mesmo método usado para reduzir o problema pode ser usado para reduzir os subproblemas.
- Mas, até quando devemos dividir o problema em subproblemas? Quando parar de reduzir? Quando o subproblema obtido for um caso trivial, para o qual se conhece a solução.
- Se o método usado para reduzir o problema for implementado como uma função, usar o mesmo método é chamar a função dentro da própria função.
- Um objeto é dito recursivo se pode ser definido em termos de si próprio;
- Recursão é o processo de se usar um objeto recursivo;
- Uma função é dita recursiva se invoca a si mesma, direta ou indiretamente;
- Exemplo:
- Os pais de uma pessoa são seus antepassados;
- Os pais de qualquer antepassado são também antepassados da pessoa em consideração;
- Toda recursão é composta por:
- Caso base:
- Uma instância do problema que pode ser solucionada facilmente;
- Chamadas Recursivas:
- O objeto define-se em termos de si próprio, procurando convergir para o caso base. Por exemplo, a soma de uma lista de n elementos pode ser definida a partir da lista da soma de n-1 elementos;
- Uma maneira mais simples de entender recursão:
- Nós já terminamos?
- Se sim, retorne os resultados;
- Se não, simplifique o problema. Resolva o problema mais simples e então encaixe os resultados na solução do problema original. Ao final, retorne a solução;
- Sem uma condição de parada como esta, uma recursão iria se repetir eternamente.
- Exemplificação
- Vantagens
- Desvantagens
- Mais detalhes
- Exemplo 01
- Exemplo 02
- Exemplo 03
- Exercício 01