Recursão e análise de algoritmos recursivos

O algoritmo recursivo é aquele que referencia a si mesmo, direta ou indiretamente. Quem chegou até aqui já está cansado de saber disso, já que a recursão é introduzida em PC I.
Dentre os aspectos importantes do algoritmo recursivo está a condição de terminação: sem ela, o algoritmo entra em loop infinito.
Exemplo de uma função recursiva:
   long fatorial(int n) {
      if ((n == 0) || (n == 1)) // condição de terminação
         return 1;
      else // caso recursivo
         return (n * fatorial(n -1));

   }
Observe que a função retorna uma chamada dela mesma com um valor uma unidade menor do que a "origem" da chamada até que este valor seja 0 ou 1.
Durante a execução de um algoritmo recursivo, vão sendo abertas novas chamadas da função conforme o tempo de execução aumenta. Portanto, o número máximo de chamadas abertas é um fator importante a ser considerado ao programar recursivamente. No exemplo do fatorial de n, n chamadas ficam empilhadas na pilha de recursão, pois cada uma espera o resultado da anterior para calcular e retornar um valor.
A recursão nunca deve ser utilizada no lugar de um laço simples. Se a chamada recursiva vier no início ou no fim do código, provavelmente pode ser substituída com facilidade por um laço.
O tempo de execução de um algoritmo recursivo é expresso por uma relação de recorrência, que é uma equação ou inequação que descreve uma função em termos de seus valores sobre entradas menores. É composta pelo caso base (conhecido) e pelo caso indutivo, que é deduzido a partir dos casos anteriores. Exemplo:

A partir da fórmula tem-se

Há o caso base (T(1) = 1) e a fórmula para descobrir um padrão.