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 |--|--|--|--|--|

1. Divide a instância para chegar a uma instância menor.
2. Resolve a instância menor.
3. 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)

Exemplo 2

Calcule \(a^b\); com \(b >= 0\); recursivamente -> \(a \cdot a \cdot ... \cdot a; b\) vezes;

1. Caso base: \(a^0 = 1\)
2. Divisão: \(a^b = a \cdot a^{b-1}\)
3. 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