Algoritmos II

Enviado por Tiago Madeira


1. Recursão

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: .

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.


Página seguinte 



As opiniões expressas em todos os documentos publicados aqui neste site são de responsabilidade exclusiva dos autores e não de Monografias.com. O objetivo de Monografias.com é disponibilizar o conhecimento para toda a sua comunidade. É de responsabilidade de cada leitor o eventual uso que venha a fazer desta informação. Em qualquer caso é obrigatória a citação bibliográfica completa, incluindo o autor e o site Monografias.com.