5 Sub-rotinas e recursão

5.1 Recursão

Muitos problemas computacionais possuem uma propriedade muito interessante: cada instância do problema pose ser subdividida em instâncias menores do mesmo problema. Assim, o algoritmo da solução para o problema é recursivo.

Em termos de programação, uma função é dita recursiva se fizer uma chamada a si mesmo. Essa característica é natural em diversas fórmulas matemáticas conhecidas. Consequentemente, diversos problemas podem ser resolvidos de maneira simples quando tratados recursivamente.

Por exemplo, definimos o fatorial de um número natural não nulo como \(n! = n \cdot (n - 1) \cdot (n - 2) \cdot \dots \cdot 1\) e fatorial de zero, \(0!\), igual a \(1\).

Sua formulação recursiva é:

\(n! = 1\) para \(n \leq 1\); e
\(n! = n \cdot (n - 1)!\) para \(n > 1\).

Traduzindo em termos computacionais, para resolver problemas recursivos, seguimos os seguintes passos:

Identificar as instâncias mínimas do problema, ou seja, aquelas que não podem ser subdivididas. Essa instância também é chamada de condição de parada do algoritmo;
Para as demais instâncias, reduzir a instância atual em instâncias menores do mesmo problema.

Vamos reproduzir esses passos para implementação de um algoritmo recursivo para calcular a soma dos números inteiros entre \(a\) e \(b\) assumindo que \(a \leq b\). Denotaremos tal soma como \(s(a, b)\).

Passo 1: A instância mínima desse problema é o caso \(a = b\) de modo que o resultado é o próprio valor de \(a\) (ou \(b\)). Ou seja, \(s(a, a) = a\).

Passo 2: Para os casos \(a < b\), podemos reduzir o problema a partir da seguinte propriedade: \(s(a, b) = s(a, c) + s(c + 1, b)\) para todo \(c\) tal que \(a \leq c < b\). Deste modo, para o caso específico \(c = a\), temos que \(s(a, b) = s(a, a) + s(a + 1, b)\).

Logo, a implementação deste algoritmo seria:

int s(int a, int b) {
  if (a == b)
    return a;
  return s(a, a) + s(a + 1, b);
}

5.1.1 Busca binária

Dada uma sequência \(v\) com \(n\) objetos ordenados de maneira crescente, queremos verificar se um determinado objeto \(k\) pertence ou não à sequência. É possível escrever um algoritmo recursivo que resolve o problema sem a necessidade de passar por cada elemento \(x \in v\).

Para construção da solução, observamos a seguinte propriedade:

Se \(k > v_i\), sabemos que \(k \neq v_j\) para todo \(j \leq i\); e
Se \(k < v_i\), que \(k \neq v_j\) para todo \(j \geq i\).

Assim, podemos construir uma solução recursiva para o problema.

Passo 1: A instância mínima acontece quando \(n = 0\) e, consequentemente, \(k \not\in v\).

Passo 2: Podemos subdividir o problema a depender do elemento \(m = v_{\lfloor n/2 \rfloor}\):

Se \(k = m\), então \(k \in v\);
Se \(k < m\), então buscamos \(k\) em \([v_j : 1 < j < \lfloor n/2 \rfloor]\); ou
Se \(k > m\), então buscamos \(k\) em \([v_j : \lfloor n/2 \rfloor < j \leq n]\).

Exercícios:

Com base na formulação recursiva do fatorial e nos passos para construção do algoritmo recursivo, implemente
Escreva um algoritmo recursivo para cálculo do \(i\)-ésimo elemento da sequência Fibonacci.
Escreva um algoritmo recursivo para cálculo do máximo divisor comum (Algoritmo de Euclides).
Implemente o algoritmo recursivo de busca binária.
Implemente uma função recursiva que calcule a soma dos dígitos decimais de um inteiro positivo.
Implemente uma função recursiva para converter número inteiro decimal em sua forma binária.
Implemente um algoritmo recursivo que calcule a representação em Gray Code usando \(N\) bits de um número \(0 \leq k \leq 2^{N-1}\).
Para todos os algoritmos anteriores, implemente uma versão iterativa.
Após ler o capitulo 8, derive qual a complexidade de tempo no pior caso da busca binária em termos do tamanho do vetor.