Formulação da recursividade

Muitos problemas computacionais são resolvidos repetindo-se uma mesma computação sobre coleções de dados de tamanho cada vez menor até que se chegue a um ponto onde não há mais necessidade de continuar esse processo. Isso é típico em problemas onde identifica-se claramente o perfil de sequência de dados. Uma das formas de expressar matematicamente uma sequência é a forma recursiva.

Em uma fórmula recursiva, cada termo é definido como uma função do seu precedente. Assim, temos que o $n-$ésimo termo da sequência é formado pelo $(n-1)-$ésimo termo mais um step. Essa etapa é conhecida por PASSO INDUTIVO da formulação.

Formalmente:

$a_n = a_{n-1} + step$

Esse passo se repete até chegarmos a um termo inicial que possui um valor definido e encerra essa recorrência. Esse termo é conhecido por CASO BASE.

$a_0 = base$

Usando a notação de funções, temos:

$f(n) = f(n-1) + step\\ f(0) = base$