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:
1. função fatorial (n)
2. se 
, então
3. retorna 
4. senão
5. retorna 
6. fim-se
7. fim-função
Domínio de nossa função: 
.
1.1. Qual o custo desse algoritmo?
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.
1. função fatorial (n)
2. se 
, então
3. retorna
4. senão
5. retorna
6. fim-se
Página seguinte  |
|
|
|
Enviado por