Recursão
É uma função que chama-se a si mesma. Os problemas que podem ser resolvidos usando recursão são problemas que possuem Estrutura Recursiva. Um problema é recursivo se toda instância do problema for composta por instâncias menores do problema.
Ex.: Encontrar o maior elemento de um vetor.
Estrutura recursiva |--|--|--|--|--|
- Divide a instância para chegar a uma instância menor.
- Resolve a instância menor.
- Combina as soluções das menores para resolver a maior.
Portanto, elaborar uma solução recursiva envolve: 1. Descobrir o caso trivial de se resolver. 2. Descobrir uma forma de dividir e... 3. Descorbir uma forma de combinar.
Utilizando o exemplo: 1. Caso base: Vetor de tamanho 1 - O maior elemento é o unico presente O(1) 2. Divisão: Reduzir as instâncias em uma unidade 3. Combinação: O maior será o maoir entre os elementos descartados e o maior da instância menor.
Código
int maio(int v[], int n){
if(n==1) return v[0];
else{
int m = maior(v, v-1);
if(m > v[v-1]) return m;
else return v[n-1];
}
}
Teste de mesa
V =
0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|
-3 | 2 | -4 | -1 | 7 |
- 7 - maior(v, 5)
- 2 - maior(v, 4)
- 2 - maior(v, 3)
- 2 - maior(v, 2)
- -3 - maior(v, 1)
- 2 - maior(v, 2)
- 2 - maior(v, 3)
- 2 - maior(v, 4)
Exemplo 2
Calcule \(a^b\); com \(b >= 0\); recursivamente -> \(a \cdot a \cdot ... \cdot a; b\) vezes;
- Caso base: \(a^0 = 1\)
- Divisão: \(a^b = a \cdot a^{b-1}\)
- Combinação = \(a \cdot a^{b-1}\)
int exp(int a, int b){
if(b==0) return 1;
else return a * exp(a, b-1);
}
- Complexidade:
- Tamanho da árvore de recursão
- Teorema mestre