Diferença entre recursão e iteração

Um método recursivo é um método que se chama direta ou indiretamente. Existem dois requisitos principais para garantir que a recursão seja bem-sucedida:

  • Toda chamada recursiva deve simplificar o cálculo de alguma maneira.
  • Deve haver casos especiais para lidar com os cálculos mais simples.

Iteração vs. Recursão

  • Se um método recursivo for chamado com um caso base, o método retornará um resultado. Se um método é chamado com um problema mais complexo, ele divide o problema em duas ou mais partes conceituais: uma peça que o método sabe fazer e uma versão um pouco menor do problema original. Como esse novo problema se parece com o problema original, o método inicia uma chamada recursiva para trabalhar no problema menor.
  • Para que a recursão termine, sempre que o método de recursão se chamar com uma versão um pouco mais simples do problema original, a sequência de problemas cada vez menores deverá convergir no caso base. Quando o método reconhece o caso base, o resultado é retornado à chamada de método anterior e uma sequência de retornos garante todo o caminho até a chamada original do método eventualmente retornar o resultado final.
  • A iteração e a recursão são baseadas em uma estrutura de controle: a iteração usa uma estrutura de repetição; recursão usa uma estrutura de seleção.
  • A iteração e a recursão envolvem repetição: a iteração usa explicitamente uma estrutura de repetição; a recursão atinge a repetição por meio de chamadas de método repetidas.
  • A iteração e a recursão envolvem um teste de terminação: a iteração termina quando a condição de continuação do loop falha; a recursão termina quando um caso base é reconhecido.
  • A iteração e a recursão podem ocorrer infinitamente: um loop infinito ocorre com a iteração se o teste de continuação do loop nunca se tornar falso; a recursão infinita ocorre se a etapa de recursão não reduzir o problema de uma maneira que converja no caso base.
  • A recursão invoca repetidamente o mecanismo e, consequentemente, a sobrecarga das chamadas de método. Isso pode ser caro no tempo do processador e no espaço de memória.

Fonte: http: //www2.hawaii.edu/~tp_200/lectureNotes/recursion.htm