Recursão matemática

Recursão é uma ideia importante usada para definir sequências de objetos, coleções mais gerais de objetos e operações sobre objetos: um objeto é definido em termos de si mesmo, mas com valores anteriores ou menores.

Sequências recursivas

Uma sequência $S$ é uma lista de objetos enumerados segundo alguma ordem: há um primeiro objeto, um segundo, e assim por diante. $S(k)$ denota o $k$-ésimo objeto da sequência. Uma definição recursiva de uma sequência possui duas partes: o(s) termo(s) inicial(is) e uma fórmula de recorrência que define $S(n)$ em função de termos anteriores.

Algoritmos recursivos

Um algoritmo é um conjunto finito de instruções precisas para realizar uma operação computacional ou resolver um problema. Um algoritmo é recursivo se resolve um problema reduzindo-o ao mesmo problema com valores iniciais menores, até alcançar um caso base que é resolvido diretamente.

function FIB(n):
begin
  if n == 0:
    return 0;
  elif n == 1:
    return 1;
  else:
    return FIB(n - 2) + FIB(n - 1);
end;

function p(a, n):
begin
  if n == 1:
    return a;
  else:
    return a * p(a, n - 1);
end;