Funções recursivas

O entendimento e a utilização de funções recursivas é uma grande arma para resolver vários tipos de problemas.  Entre os problemas que são mais fáceis serem resolvidos usando métodos recursivos estão os problemas de contagem. Em alguns casos, o próprio processo que precisamos contar é descrito de maneira recursiva.

Em geral, os algoritmos recursivos são mais fáceis de serem entendidos e mais fáceis de provar a corretude dos mesmos. 

Considere o seguinte problema Cola:

A cada três garrafas devolvidas vazias de Choco Cola, ganhe um nova garrafa de Choco Cola.

Se você comprar N garrafas de Choco Cola na loja, quantos refrigerantes você vai conseguir realizando todas as trocas possíveis?

Seja T(n) o número de refrigerante que você pode conseguir realizando todas as trocas possíveis.

Recorrência dada pelo professor Fábio Carlos.

$$T(n) = \begin{cases}n & n < 3 \\ 3 + T(n-3+1) & \text{caso contrário,} \end{cases}$$

Observe que a cada três refrigerantes, ele ganha um novo refrigerante. Teste 

Podemos acelerar a recorrência acima da seguinte maneira:

$$T(n) = \begin{cases}n & n < 3 \\ 3* \lfloor n/3 \rfloor + T(n - 3 \lfloor n/3 \rfloor + \lfloor n/3 \rfloor) & \text{caso contrário,} \end{cases}$$

Esta solução é equivalente a solução dada pelo aluno Alexsandro Oliveira.

$$T(n) = \begin{cases}n & n < 3 \\ n - n \text{ mod } 3 + T(n \text{ mod } 3 + \lfloor n/3 \rfloor ) & \text{caso contrário,} \end{cases}$$

Esta outra recorrência também resolve o mesmo problema:

$$T(n,m) = \begin{cases}n & n+m < 3 \\ n + T( \lfloor (n+m)/3 \rfloor , (n+m) \text{ mod } 3 ) & \text{caso contrário,} \end{cases}$$