A recursão é uma das técnicas mais simples e úteis que existem para usarmos em nossos algoritmos. Consiste em uma função (denominada recursiva) chamar a si mesmo, até que o retorno seja trivial. Resolvi abordá-la aqui porque alguns algoritmos que estudaremos mais para frente usam funções recursivas.

Em matemática, o número fatorial de é igual a: .

Logo, por exemplo, (cinco fatorial) seria igual a: .

Um exemplo bom e simples de recursão é um algoritmo para determinar números fatoriais:

Vamos abrir um grande parênteses aqui até a próxima linha horizontal para descobrir qual o custo do nosso algoritmo antes de continuar com a conversa sobre recursão e relembrar/reforçar o post sobre Análise de Algoritmos. Vou colocar o número de vezes que cada instrução é executada, usando o esquema que será o padrão para as próximas vezes que veremos custos:

Número da linha: Número de vezes que é executada..

Uma função linear, o tipo de algoritmo mais simples que podemos encontrar, com excessão dos que são uma função constante. Mas o parênteses na verdade não serviu só pra isso. Eu queria aproveitar pra escovar uns bits de nosso código. Você percebeu que o primeiro condicional é executado vezes, mas só entramos nele uma vez? Então vamos inverter nosso condicional.