Algoritmo e Estrutura de Dados - UFRP

Prévia do material em texto

Recife,2009
Algoritmos e 
Estrutura de Dados
Rodrigo de Souza
Hugo Rodrigues
Universidade Federal Rural de Pernambuco
Reitor: Prof. Valmar Corrêa de Andrade
Vice-Reitor: Prof. Reginaldo Barros
Pró-Reitor de Administração: Prof. Francisco Fernando Ramos Carvalho
Pró-Reitor de Extensão: Prof. Paulo Donizeti Siepierski
Pró-Reitor de Pesquisa e Pós-Graduação: Prof. Fernando José Freire
Pró-Reitor de Planejamento: Prof. Rinaldo Luiz Caraciolo Ferreira
Pró-Reitora de Ensino de Graduação: Profª. Maria José de Sena
Coordenação Geral de Ensino a Distância: Profª Marizete Silva Santos
Produção Gráfica e Editorial
Capa e Editoração: Allyson Vila Nova, Rafael Lira e Italo Amorim
Revisão Ortográfica: Marcelo Melo
Ilustrações: Roberto Costa e Diego Almeida
Coordenação de Produção: Marizete Silva Santos
Sumário
Plano da Disciplina ...............................................................................4
Apresentação ........................................................................................7
Conhecendo o Volume 1 ......................................................................8
Capítulo 1 – História do conceito de algoritmo .................................9
1. O que é um algoritmo? ...................................................................9
2. De onde vem a ideia de algoritmo? ..............................................11
3. Algoritmos versus programas .......................................................13
Capítulo 2 – Exemplos de algoritmos ...............................................19
1. O algoritmo de Euclides ................................................................20
2. A linguagem Portucal ....................................................................23
Capítulo 3 – Algoritmos recursivos ...................................................42
1. O conceito de recursão .................................................................42
2. Deve-se sempre usar recursão? ..................................................46
Capítulo 4 – Análise de um algoritmo ...............................................50
1. Uma experiência: eficiência de soma-subconjunto ......................51
2. Análise assintótica ........................................................................58
Considerações Finais ........................................................................66
Conheça os Autores ..............................................................................68
Plano da Disciplina
Disciplina: Algoritmos e Estruturas de Dados
Carga horária: 60h
» Ementa da Disciplina: História do conceito de algoritmo. Notação para 
apresentação de algoritmos. Algoritmos recursivos. Noções de análise de 
algoritmos, notação assintótica. Operações básicas em vetores e matrizes. Busca 
binária. Algoritmos de ordenação: inserção, seleção, flutuação, intercalação, 
quicksort. Listas ligadas, pilhas e filas. Árvores binárias, árvores balanceadas. 
Tabelas de espalhamento. Busca de palavras em um texto. Noções de grafos, 
algoritmo de Dijkstra.
Objetivos
Objetivo Geral
• Fixar o conceito de algoritmo e introduzir algoritmos eficientes para manipulação 
de dados
• Apresentar estruturas de dados fundamentais
Objetivos Específicos
• Fornecer ao aluno uma noção da história e da importância da noção de algoritmo, 
bem como rudimentos de análise de complexidade e correção de algoritmos, 
facultando-o a discernir entre possibilidades diversas para a solução de um 
problema computacional e habilitando-o a desenvolver algoritmos eficientes. 
Introduzir e analisar algoritmos clássicos de busca e ordenação.
• Apresentar estruturas de dados fundamentais, bem como suas operações básicas 
e algoritmos associados.
Conteúdo Programático
Módulo 1 – Noções básicas de algoritmos
Carga horária: 15h
• História do conceito de algoritmo
• Notação para apresentação de algoritmos
• Algoritmos recursivos
• Noções de análise de algoritmos, notação assintótica
Módulo 2 – Busca e ordenação em vetores
Carga horária: 15h
• Primeiras noções de estruturas de dados
• Busca, inserção e remoção em vetores
• Algoritmos elementares de ordenação
• Ordenação mais eficiente: intercalação
Módulo 3 – Estruturas de dados elementares
Carga horária: 15h
• Listas ligadas
• Pilhas
• Filas
• Árvores
Módulo 4 – Tópicos adicionais
Carga horária: 15h
• Tabelas de espelhamento
• Busca de palavras em um texto
• Noções de grafos, algoritmo de Dijkstra
Avaliação
 60% atividades presenciais realizadas nos pólos (provas e exercícios de 
programação simples)
 40% atividades nos ambientes virtuais de aprendizagem (participação, discussão 
em tempo real de questões propostas pelo professor)
Metodologia
 Uso de recursos visuais para animação e ilustração dos algoritmos e estruturas 
de dados estudados, uso de fórum de discussão para tratamento de dúvidas e 
discussão de problemas propostos na disciplina, realização de exercícios propostos 
pelo professor (listas ou exercícios de programação). Havendo possibilidade, uso 
de recursos interativos (applets Java, por exemplo), facultando ao aluno realizar 
com mouse/teclado operações básicas em estruturas de dados.
Referências
 CORMEN, T; LEISERSON, C; RIVEST, R; STEIN, C. Algoritmos - Teoria e 
Prática. São Paulo: Ed. Campus, 2002.
 TERADA, R.; SETzER, V. W. Introdução à Computação e à Construção de 
Algoritmos. São Paulo: Makron Books, 1992.
 KNUTH, D. The Art of Computer Programming. Massachusetts: Addison-
Wesley, 1997
 WIRTH, N. Algoritmos e Estruturas de Dados. Rio de Janeiro: Ed. Prentice Hall 
do Brasil, 2002.
Apresentação
Caro(a) cursista
Seja bem-vindo(a) ao primeiro módulo do curso Algoritmos e Estruturas de Dados. 
Nele, teremos nosso primeiro contato com o conceito de algoritmo, que é fundamental 
em Computação, pois algoritmos são a essência de qualquer programa em execução 
num computador real.
Começaremos esse volume com um pouco de História. Veremos que algoritmos já 
eram utilizados por civilizações da Antiguidade e que a formalização desse conceito foi 
uma das descobertas mais importantes do século vinte para a Computação.
Vamos, logo em seguida, estudar nossos primeiros algoritmos. Veremos que 
podemos descrever algoritmos com uma linguagem bastante simples e natural, e não 
muito distante das linguagens de programação populares. Também descobriremos 
que um algoritmo pode, em sua execução, iniciar uma nova execução de si mesmo, 
e que esse recurso é bastante poderoso. Tais algoritmos são chamados de algoritmos 
recursivos.
Finalmente, consideraremos o fato de que, normalmente, podemos resolver um 
problema de diversas maneiras, ou seja, usando uma variedade de algoritmos. Contudo, 
perceberemos que certos algoritmos podem ser mais eficientes do que outros. Para 
isso, vamos introduzir uma ferramenta para medir a eficiência de algoritmos, a análise 
de complexidade.
Bons estudos!
Professores Rodrigo de Souza e Hugo Rodrigues 
8
Algoritmos e Estrutura de Dados
Conhecendo o Volume 1
Neste primeiro volume, você irá encontrar o módulo 01 da disciplina 
Algoritmos e Estruturas de Dados. Para facilitar seus estudos, veja 
a organização deste primeiro módulo.
Módulo 1 – Noções básicas de algoritmos
Carga horária do Módulo 1: 15h/aula
Objetivo do Módulo 1: Introduzir os conceitos de algoritmo e 
algoritmo recursivo. Fixar uma notação para apresentação de 
algoritmos. Introduzir elementos de análise de algoritmos.
Conteúdo Programático do Módulo 1
• História do conceito de algoritmo
• Exemplos de algoritmos
• Algoritmos recursivos
• Noções de análise de algoritmos, notação assintótica
9
Algoritmos e Estrutura de Dados
Capítulo 1 – História do 
conceito de algoritmo
Vamos conversar sobre o assunto?
Você provavelmente já usou um computador para alguma tarefa 
cotidiana – escrever uma carta, comunicar-se por e-mail, calcular 
suas despesas, orientar-se através de um GPS de bordo... Talvez 
já tenha precisado buscar uma palavra num texto, executar uma 
operação repetidanuma planilha, ou determinar o caminho mínimo 
entre dois pontos em um mapa para percorrer com seu veículo. Já 
parou para pensar como o computador encontra a solução para esses 
problemas? Ou então já se perguntou se os computadores podem 
resolver qualquer problema?
Do ponto de vista do usuário, o computador é uma caixa preta 
que lhe fornece certas funcionalidades – como um eletrodoméstico 
comum. Para o estudioso de Computação, o computador, como 
objeto não-pensante, é meramente um mecanismo executor de 
sequências precisas de instruções. Tais sequências de instruções são 
o que chamamos de algoritmos. Algoritmos são, assim, o princípio do 
funcionamento de qualquer computador, e mais: desde a Antiguidade, 
o homem executa algoritmos, e é possível que cada um de nós tenha 
executado, ao longo de nossas vidas, algoritmos diversos. Quem 
nunca precisou ordenar as cartas de um baralho ou de um fichário? 
A noção de algoritmo, sendo natural, pode ser compreendida 
mesmo por quem não utiliza computadores. É com esse espírito que 
vamos estudá-los nesse volume. Por outro lado, o domínio da noção 
de algoritmos vai nos fornecer uma compreensão mais profunda dos 
limites dos computadores e uma visão diferente da do usuário comum. 
Bom estudo!
1. O que é um algoritmo?
De forma geral, um algoritmo é uma sequência finita de instruções. 
Uma receita de cozinha, se bem definida (especificando-se as 
quantidades de cada ingrediente e como eles serão misturados, 
por exemplo), é um algoritmo legítimo! Toda receita bem definida 
especifica com precisão os passos necessários para a elaboração 
10
Algoritmos e Estrutura de Dados
de um produto final. A execução de um algoritmo, nesse exemplo 
culinário, é simplesmente seguir a receita criteriosamente, passo a 
passo. Portanto, um algoritmo não tem necessariamente relação com 
um computador digital.
Mas essa definição parece muito geral e, para o estudioso de 
Computação, uma definição formal é necessária. De fato, esse 
estudioso desejará demonstrar fatos sobre algoritmos – o quão 
eficiente um algoritmo pode ser, se o mesmo resolve corretamente o 
problema a que se propõe solucionar. Não é à toa que muitas vezes 
a Computação confunde-se com a Matemática. Dessa forma, qual a 
resposta definitiva à nossa questão, “O que é um algoritmo?”
A resposta parece misteriosa, mas é simples. Vamos respondê-
la com alguma precisão no Capítulo 2, onde entraremos em acordo 
sobre uma notação para apresentação de algoritmos. Por enquanto, 
podemos manter em mente a idéia intuitiva de sequência de instruções, 
com algumas restrições importantes:
• essa sequência é finita;
• cada instrução pode ser executada de forma finita e mecânica 
(por um ser-humano usando apenas lápis e papel, por 
exemplo);
• o conjunto de instruções possíveis é finito.
Essas restrições são importantes: se tudo é permitido, então a 
noção de algoritmo perde o interesse do ponto de vista prático. Quem 
quer esperar toda a eternidade para saber o saldo de sua conta 
quando vai consultar um terminal eletrônico?
Também é preciso considerar que um algoritmo dialoga com o 
mundo externo. Ele recebe uma entrada, alguma informação a ser 
processada, e fornece uma saída, o resultado desse processamento. 
11
Algoritmos e Estrutura de Dados
No exemplo da receita, a entrada são os ingredientes, a saída é o 
produto que vamos cozinhar – um bolo, por exemplo.
Dissemos que a resposta é misteriosa, mas é simples. Também 
poderíamos dizer: a resposta é simples, mas por um bom tempo, 
foi misteriosa. A seguir, vamos sobrevoar o caminho trilhado pela 
civilização até a conquista da ideia precisa de algoritmos.
2. De onde vem a ideia de algoritmo?
A etimologia da palavra algoritmo revela um pouco de sua história. 
Historiadores da Matemática concluíram que ela vem do nome de um 
matemático persa do século nove, Abu Já’far Mohammed ibn Mûsâ 
Al-Khowârizmî. Literalmente: “Pai de Ja’far Mohammed, filho de 
Moisés, nativo de Khowârizm”. Al-Khowârizmî deu origem, durante 
a Idade Média, ao termo algoritmo (seu nome foi latinizado como 
Algorismus), e este foi usado com significados diversos. Por exemplo, 
alguns dicionários antigos definem essa palavra como todo processo 
de cálculo combinando às quatro operações aritméticas fundamentais. 
O que é compreensível, pois Al-Khowârizmî era um autor importante 
de livros matemáticos, e supostamente inventou algoritmos para a 
realização dessas operações.
Mas como dissemos, algoritmos são processos que ocorrem 
naturalmente em nosso dia-a-dia, sendo nós estudiosos da 
Computação ou não. Mencionamos o exemplo da cozinha. Poderíamos 
considerar também o processo de montagem de uma estante, ou da 
busca de um nome numa lista telefônica. Dessa forma, fica evidente 
que desde a Antiguidade o homem imagina e executa algoritmos em 
sua rotina. E com relação a algoritmos mais complexos, como os que 
são executados mecanicamente por computadores?
Como você ordena 
comumente um baralho? 
 
Será que você utiliza algum 
algoritmo para isso?
12
Algoritmos e Estrutura de Dados
Novamente, voltamos à Antiguidade: desde há muito tempo, o 
homem executa algoritmo não tão simples para realizar operações 
com números. Considera-se como primeiro exemplo de algoritmo 
não-trivial um procedimento descrito entre 400 e 300 antes de Cristo 
pelo matemático grego Euclides para encontrar o maior divisor comum 
entre dois números. O algoritmo de Euclides é hoje universalmente 
conhecido. Vamos ainda nesse módulo entender como ele funciona.
Da Antiguidade até hoje, além da invenção de novos algoritmos, 
o homem também se preocupou com a invenção de máquinas para 
executá-los. O exemplo mais clássico é o ábaco, que permite a 
realização de operações aritméticas com rapidez (de fato, a realização 
de uma operação aritmética obedece a um algoritmo, e tais algoritmos 
são introduzidos às crianças nos primeiros anos escolares). No 
século XIX, alguns nomes se destacam por tentativas de construção 
de máquinas executoras de instruções: o francês Joseph Jacquard, 
o inglês Charles Babbage e o estadunidense Herman Hollerith. Em 
particular, a máquina de Hollerith, que usava cartões perfurados, 
foi usada com sucesso no censo dos Estados Unidos de 1890. Tais 
máquinas foram precursoras dos computadores modernos.
Figura 1 - Três máquinas projetadas para auxiliar na execução de algoritmos: um ábaco, 
uma máquina de cartão perfurado e um computador.
O passo definitivo para a compreensão do conceito de algoritmo, 
tal como o conhecemos atualmente, foi dado no início do século 
XX. O termo “procedimento efetivo”, que podemos entender como 
“método possível de realizar por meios mecânicos”, pairava no ar 
entre os matemáticos dessa época. Mas uma definição formal dessa 
idéia estava em falta. Questões como “encontre um procedimento 
efetivo para testar se uma fórmula é logicamente válida“ estavam 
13
Algoritmos e Estrutura de Dados
na moda, mas ficavam sem resposta. Mesmo antes do surgimento 
dos computadores, o matemático britânico Alan Turing imaginou um 
dispositivo abstrato que supriu essa lacuna. Esse dispositivo, hoje 
conhecido como máquina de Turing, apesar de bastante simples, é 
equivalente a qualquer computador real. E a pesquisa ao longo do 
século XX mostrou que todos os algoritmos conhecidos até então, 
desde o algoritmo de Euclides, podem, após uma certa transformação, 
ser vistos como uma máquina de Turing.
Essa descoberta de Turing foi uma das mais importantes para a 
Computação. Com ela, a noção de algoritmo ganhou uma definição 
formal razoável e cresceu em importância. O surgimento dos 
computadores digitais, poucos anos em seguida, veio em boa hora.
A tese de Church
As máquinas de Turing são atualmente aceitas como o modelo descritivo do 
conceito de algoritmo. No entanto, a discussão a respeito desse conceito não 
está concluída. Quem garantirá que a idéia vaga de procedimento efetivo 
corresponde de fato às máquina de Turing? Existirá na Natureza algum 
procedimentomecânico que não possa ser realizado por uma máquina 
de Turing? Essa questão, que beira a filosofia, é conhecida como tese de 
Church, em homenagem ao lógico Alonzo Church cujas pesquisas foram 
bastante importantes para a nascente Ciência da Computação.
3. Algoritmos versus programas
Às vezes os termos algoritmo e programa são usados como 
sinônimos. De fato, algoritmos hoje estão tão associados a 
computadores que costumamos pensar neles como um programa, 
que escrevemos numa linguagem como o C ou o Java. Mas há uma 
diferença aqui. Como acabamos de estudar, a ideia de algoritmo 
independe da existência de computadores digitais ou de linguagens 
de programação. Euclides certamente não pensava em computadores 
quando imaginou seu método para determinar o maior divisor comum 
entre dois números. Podemos executá-lo com lápis e papel.
Um programa é uma sequência de instruções em determinada 
linguagem de programação. Assim, programas em linguagens 
diferentes normalmente são diferentes, pois obedecem a regras de 
sintaxe distintas. Mas programas diferentes podem funcionar de 
maneira análoga. De fato, tipicamente um programa codifica algum 
14
Algoritmos e Estrutura de Dados
algoritmo. Dizemos que o algoritmo foi implementado. Um algoritmo 
pode ser implementado em linguagens diversas, de maneiras diversas. 
O algoritmo é o mesmo. A linguagem é preferência nossa.
Um algoritmo pode ser implementado em diversas linguagens.
Uma profissão muito em voga entre os egressos de um curso de 
Computação é a de programador. Um programador é um especialista 
em escrever programas de computador e geralmente conhece 
diversas linguagens de programação e tecnologias. Um programador, 
no entanto, não é necessariamente um projetista de algoritmos. Uma 
boa analogia aparece ao se pensar em compositores e pianistas. O 
pianista não é necessariamente um compositor, mas é especialista 
em realizar aquilo que o compositor imagina. E o compositor não é 
necessariamente um pianista exímio – apesar de existirem exemplos 
de grandes compositores que também eram bons pianistas, e de bons 
projetistas de algoritmos que programam muito bem. Um não pode 
prescindir do outro: um algoritmo complicado, projetado para realizar 
maravilhas em um computador, permanecerá no mundo das ideias 
sem um programador que o faça existir no mundo real.
Atualmente, a busca de algoritmos eficientes tornou-se uma área de 
pesquisa bastante ativa, especialmente na academia, mas também na 
indústria. Na prática, todas as aplicações de computadores podem se 
beneficiar com o resultado da pesquisa de novos algoritmos. Para citar 
alguns exemplos característicos: criptografia, sistemas operacionais, 
computação gráfica e bancos de dados são subáreas da Computação 
que dependem amplamente de algoritmos. Ademais, essa pesquisa 
esconde alguns dos problemas mais desafiadores em Computação. 
Existem problemas para os quais nenhum algoritmo eficiente é 
15
Algoritmos e Estrutura de Dados
conhecido. Para alguns deles, a execução dos melhores algoritmos 
conhecidos, no melhor computador atual, consumiria séculos para 
terminar. E há pior: para determinados problemas, nenhum algoritmo 
é possível (tais problemas são chamados de indecidíveis) Esses 
estudos ilustram bem os limites dos computadores.
Em suma, sempre que fizermos, com um computador, uma busca 
na Internet, ou o desenho de um gráfico, podemos imaginar que por 
trás da interface gráfica com o usuário, do aplicativo em execução, do 
processador, encontramos a execução de muitos algoritmos. Projetar 
bons algoritmos é, portanto, essencial para garantir a realização de 
tarefas com eficácia num computador. É pelo menos tão importante 
quanto o aprendizado de linguagens de programação.
Conheça Mais
Computadores nem são tão antigos, mas alguns deles já estão 
virando objeto de museu. Você pode consultar muitos fatos sobre a 
história dessas máquinas em
 http://www.computerhistory.org/
Para uma fonte em Língua Portuguesa, consulte
 http://www.ime.usp.br/~macmulti/historico/
Um dos mais ilustres cientistas da Computação é o estadunidense 
Donald Knuth. Além de ser responsável por muitas contribuições 
importantes ao estudo de algoritmos e programação de computadores, 
ele vem trabalhando desde a década de 1970 numa coleção 
enciclopédica chamada “The Art of Computer Programming”. Nos 
volumes já publicados – três no total – muitos dos principais algoritmos 
e técnicas de programação conhecidos são tratados com detalhes, e 
notas históricas bastante interessantes são discutidas. Mais detalhes 
na página do autor:
 http://www-cs-faculty.stanford.edu/~uno/taocp.html
Uma referência recente e bastante completa sobre algoritmos é o 
livro
 Cormen, T; Leiserson, C; Rivest, R; Stein, C. Algoritmos - 
Teoria e Prática. São Paulo: Ed. Campus, 2002.
16
Algoritmos e Estrutura de Dados
Você Sabia?
Você sabia que o termo holerite, usado informalmente como 
sinônimo de demonstrativo de vencimentos, vem do nome do 
engenheiro estadunidense Herman Hollerith?
Hollerith foi o inventor de uma máquina de cartões perfurados que 
ajudou na execução do censo dos Estados Unidos em 1980. Essa 
máquina foi uma das precursoras dos computadores programáveis e 
a fusão de sua empresa com outras companhias deu origem à IBM.
Webquest 1: História da Computação
Vamos aprofundar nosso conhecimento sobre a História da 
Computação através de uma Webquest. Nela, você pesquisará na 
Internet contribuições importantes para a evolução dessa ciência.
Introdução
Conforme estudamos, o homem elabora algoritmos há muito 
mais tempo do que o advento dos computadores digitais. Nessa 
tarefa, faremos um panorama da evolução desse conceito de forma 
esquemática.
A Ciência da Computação é considerada uma ciência recente. 
No entanto, busque notar durante a elaboração da sua pesquisa 
que algumas ideias fundamentais para essa ciência já existiam nos 
séculos passados.
A Tarefa
Agora, você será o historiador.
Sua missão é elaborar uma linha do tempo, especificando datas, 
personagens e descobertas importantes para a Computação. 
Você pode, por exemplo, iniciar com o algoritmo de Euclides, 
especificando brevemente quem foi Euclides, e em que obra esse 
algoritmo foi descrito. Em seguida, fazer o mesmo para outras 
contribuições, incluindo aquelas consideradas no texto desse módulo. 
Personagens como Jacquard, Babbage e Turing devem figurar nessa 
linha do tempo – mas você pode incluir outros não mencionados que 
17
Algoritmos e Estrutura de Dados
encontrar.
Por exemplo, tente descobrir quem foi Ada Lovelace (ela é 
considerada a primeira programadora da História). Também tente 
descobrir alguns nomes importantes que fizeram contribuições 
recentes ao estudo de algoritmos, e quais foram essas contribuições. 
Você pode, por exemplo, fazer sua pesquisa entre os vencedores do 
prêmio Turing, um dos mais prestigiosos em Computação. Certamente 
você se deparará com alguns dos autores dos livros mencionados 
nesse curso.
O Processo
Para elaborar sua linha do tempo, consulte os endereços 
sugeridos na seção “Conheça mais”. Você pode também acessar 
outros endereços: certamente uma busca na Internet vai revelar 
muitos locais interessantes para pesquisa. Busque por palavras-
chave de natureza diversa: nomes de personagens (Babbage, 
Turing), de conceitos (algoritmo), de algoritmos particulares (algoritmo 
de Euclides, algoritmos de ordenação), etc. Organize sua linha do 
tempo especificando, para cada evento interessante, personagens 
envolvidos (se algum), contribuição e influência. Se encontrar relações 
entre eventos, não deixe de mencioná-las.
Compare sua linha do tempo com a de seus colegas, e preencha 
lacunas, de maneira a torná-la bastante completa.
Avaliação
Na avaliação da atividade, serão observados os seguintes 
critérios:
a) A riqueza de informações da linha do tempo (que deve incluir 
pelo menos os eventos mencionados neste capítulo).
b) A compreensão do significado e importância de cada eventoespecificado.
c) A competência do educando nos processos de discussão on-
line sobre as etapas de pesquisa e de produção da atividade. 
Será avaliada a participação significativa do aluno nos fóruns 
de discussão orientados pelos tutores.
18
Algoritmos e Estrutura de Dados
Conclusão
Caro(a) aluno(a),
A elaboração dessa linha do tempo não apenas o levou a adquirir 
uma visão panorâmica da História da Computação, mas também 
o ajudou a compreender e fixar a noção de algoritmo, que é muito 
anterior ao advento dos computadores.
Procure conversar mais a respeito com amigos que trabalham 
com Informática. Descubra se essa noção também é clara para eles. 
Observe ao seu redor, atente para suas tarefas, e busque identificar 
quais escondem uma sequência de passos semelhante a um algoritmo. 
Essa preparação é importante para o próximo capítulo.
Referências
As referências mencionadas na seção “Conheça mais” trazem 
muitas informações a respeito da História da Computação. Para outra 
fonte consulte também
 http://www.cs.uwaterloo.ca/~shallit/Courses/134/history.html
A página do professor Waldemar Setzer da Universidade de São 
Paulo contém muitos artigos e apresentações sobre a história dos 
computadores e assuntos relacionados. Consulte:
 http://www.ime.usp.br/~vwsetzer/apresentacoes/
Vamos revisar?
Neste capítulo, descobrimos que a noção de algoritmo, que é 
subjacente ao processamento realizado por computadores, tem 
suas origens na Antiguidade. Vimos que ao longo da História a 
humanidade preocupou-se em projetar algoritmos e máquinas para 
executá-los, culminando com a invenção dos computadores no século 
XX. Também compreendemos que a noção de algoritmo é bastante 
natural, e pode ser identificada com a de receita para a realização de 
uma tarefa. No entanto, essa noção intuitiva só recebeu uma definição 
formal aceitável no início do século XX. Finalmente, consideramos 
que algoritmos e programas são conceitos distintos, mesmo que na 
prática sejam tratados como sinônimos.
19
Algoritmos e Estrutura de Dados
Capítulo 2 – Exemplos de 
algoritmos
Vamos conversar sobre o assunto?
Algoritmos, conforme vimos no capítulo anterior, são sequências de 
instruções, ou receitas bem definidas, projetadas para a manipulação 
ou transformação de um certo conjunto de dados. Com essa noção 
intuitiva em mente, vimos que ao longo da História o homem se 
preocupou em inventar algoritmos e máquinas para executá-los.
Recorde nosso objetivo principal nessa disciplina: adquirir a 
capacidade de imaginar nossos próprios algoritmos para problemas 
práticos, descobrir ferramentas poderosas para o projeto de algoritmos 
eficientes e implementá-los em um computador. Vamos, nesse 
capítulo, dar um passo adicional em direção a esse objetivo.
Começaremos analisando o algoritmo de Euclides, que calcula o 
máximo divisor comum entre dois números inteiros. Vamos descrever 
esse algoritmo em Português, de maneira muito próxima a uma receita 
de bolo. Também vamos simulá-lo, ou seja, executar essa receita. 
Em seguida, vamos estudar uma linguagem para a apresentação 
de algoritmos, mais próxima das linguagens de programação 
usadas para implementações em computadores. Veremos que essa 
linguagem não é tão diferente da receita de bolo, mas é, ao mesmo 
tempo, suficientemente próxima das linguagens de programação para 
uma tradução quase imediata. Essa linguagem, que chamamos de 
Portucal, permite a descrição de um algoritmo de maneira precisa, 
usando algumas poucas palavras em Língua Portuguesa.
Antes de prosseguirmos nosso estudo nos capítulos seguintes, 
vamos exercitar bastante nossa experiência de criação de algoritmos 
usando a linguagem Portucal. Veremos posteriormente que essa 
prática é a essência do desenvolvimento de algoritmos e estruturas 
de dados: não pensar em linguagens de programação ou tecnologias 
específicas, mas pensar no problema e em métodos eficientes para 
resolvê-lo. Dessa forma, estudaremos exemplos, desenvolveremos 
algoritmos para alguns problemas interessantes, e aprenderemos a 
demonstrar que nosso algoritmo é correto. Bom estudo!
20
Algoritmos e Estrutura de Dados
1. O algoritmo de Euclides
Dentre as contribuições dos gregos da Antiguidade Clássica à 
nossa civilização, a Matemática estudada por eles é certamente uma 
das mais importantes. Muitas propriedades dos números e dos objetos 
geométricos que conhecemos atualmente vieram de indagações 
filosóficas dos gregos, e foram, felizmente, preservadas em obras 
escritas que sobreviveram à passagem do tempo.
Uma dessas obras é a coleção Elementos, do matemático Euclides. 
O ponto de partida do presente capítulo é a análise de dois assuntos 
expostos nos livros 7 e 10 dessa coleção. 
O primeiro é o conceito de divisão inteira, que é largamente 
difundido no ensino de Matemática. Dados dois números inteiros, 
que podemos chamar de a e b, e onde b é diferente de 0, sempre é 
possível encontrar dois números inteiros q (chamado quociente) e r 
(chamado resto) que satisfazem
0 ≤ r < b, ou seja: r é menor ou igual a zero e, ao mesmo tempo, 
r é menor que b
a = bq + r, ou seja: o valor de a será igual ao valor de b multiplicado 
pelo quociente (da divisão de a por b) somado com o resto (também 
da divisão de a por b)
Por exemplo, para
a = 16, b = 6
o quociente e o resto são
q = 2, r = 4
Além disso, o quociente e o resto são únicos: cada par de números 
tem seu quociente e seu resto; não existem dois outros números que 
satisfaçam essas propriedades na divisão de a por b. Se o resto r é 
igual a zero, então temos uma situação de divisão exata. Neste caso, 
dizemos que b divide a, ou que a é divisível por b.
O segundo conceito é o máximo divisor comum. Dados dois inteiros 
m e n, existe um inteiro d com as seguintes propriedades:
1. d divide m e d divide n;
2. não existe inteiro maior do que d e que divide m e n.
Em outras palavras: d é o maior inteiro que divide tanto m quanto 
21
Algoritmos e Estrutura de Dados
n. Daí o nome “máximo divisor comum”. O máximo divisor comum 
dos números 16 e 6 é 2 porque qualquer outro número inteiro maior 
que 2 não divide ao mesmo tempo 16 e 6. Por exemplo, o número 4 
divide 16 (quociente = 4 e resto = 0), mas não divide 6 (quociente=1 
e resto=2). Já o número 3 divide 6 (quociente=2 e resto=0), mas não 
divide 16 (quociente=5 e resto=1).
Nos Elementos, Euclides descreveu um método para calcular o 
máximo divisor comum entre dois números (aparentemente, esse 
método já era conhecido antes dessa época). Trata-se de uma receita 
simples, composta por uma sequência de instruções precisas que 
podemos executar mecanicamente com lápis e papel – um algoritmo, 
portanto. Vejamos uma descrição desse algoritmo em Português. Em 
seguida, vamos analisá-la com cuidado.
Algoritmo de EUCLIDES
Encontra o máximo divisor comum entre dois inteiros m e n
Passo 1: Adote como valores de x e y os valores de m e n, respectivamente:
Passo 2: Adote como valor de r o resto da divisão do valor de x pelo valor de y;
Passo 3: Adote como novo valor de x o valor de y, e como novo valor de y o valor 
de r;
Passo 4: Se o valor de r é nulo, então o valor de x é o máximo divisor comum 
procurado, e o cálculo termina; senão, volte para o Passo 2.
Essa receita de quatro passos, a despeito de sua simplicidade, já 
introduz alguns conceitos que nos acompanharão ao longo de toda a 
disciplina. 
Primeiro, devemos estar atentos ao fato de que a receita lida com 
valores desconhecidos de antemão. De fato, não desejamos saber 
o máximo divisor comum entre 16 e 6, ou outro par de números em 
particular. Desejamos que nosso método seja capaz de encontrar uma 
resposta para qualquer par de números inteiros.
Esses valores são fornecidos pelo usuário do algoritmo. Como 
se costuma dizer, eles são a entrada do algoritmo, ou ainda, uma 
instância do problema de encontrar o máximo divisor comum. No 
caso, esses valores são representados pelas letras m e n.
Além de m e n, o algoritmo usa as letras x, y e r, e os valoresrepresentados por elas são modificados constantemente ao longo de 
22
Algoritmos e Estrutura de Dados
uma execução do algoritmo. Tais letras que representam valores, que 
podem ser usados, intercambiados, modificados, são chamadas de 
variáveis. Na execução de um algoritmo em um computador digital, 
as variáveis representam posições de memória contendo os valores 
manipulados.
Notamos também que o algoritmo usa no Passo 2 a operação de 
divisão inteira sem descrever como ela é executada. Embora a divisão 
inteira também seja um algoritmo, podemos assumir que possuímos 
uma calculadora que a realize. Ou seja, o algoritmo conta com um 
recurso externo, outro algoritmo, capaz de executar a divisão inteira.
Nós dissemos o que o algoritmo de Euclides faz – calcula o 
máximo divisor comum entre dois números – mas não provamos que 
ele realmente funciona. É importante ter em mente que a prática do 
desenvolvimento de algoritmos exige um certo rigor matemático para 
ser bem-sucedida: só vamos nos convencer a usar um algoritmo 
mediante uma prova de sua corretude, ou seja, uma prova de que ele 
sempre dá a resposta correta.
Não vamos aqui entrar nesses detalhes para o algoritmo de 
Euclides, embora seja um bom exercício tentar demonstrar que ele 
funciona. No momento, nossa preocupação será o entendimento 
de cada um dos passos desse algoritmo, e para isso faremos uma 
simulação.
Simular significa assumir o papel do computador, ou de qualquer 
máquina executora de algoritmos. De posse de lápis e papel, 
vamos acompanhar a execução do algoritmo de Euclides para uma 
determinada instância do problema. Como já conhecemos o resultado 
para o máximo divisor comum dos números 16 e 6, este é um bom 
exemplo inicial. Faremos isso anotando os valores das variáveis em 
uma tabela: cada coluna corresponde a uma variável, e as linhas 
indicam os valores assumidos sucessivamente por essas variáveis.
x y r
16 6 4
6 4 2
4 2 0
2 0
23
Algoritmos e Estrutura de Dados
Ao final da execução, quando a variável r assume o valor nulo 
(conforme é mostrado no quarto passo do algoritmo de Euclides), 
a variável x assume o valor 2 e, portanto, este é o máximo divisor 
comum entre 16 e 6. Dizemos esse é o valor devolvido ou retornado 
pelo algoritmo. 
Para ilustração de que o algoritmo funciona para qualquer outro 
par de inteiros, vamos simulá-lo novamente, agora com uma instância 
do problema um pouco mais complexa, os números 348 e 156. 
x y r
348 156 36
156 36 12
36 12 0
12 0
Ao final da execução, a variável x vale 12, que é o máximo divisor 
comum entre 348 e 156. A fim de se familiarizar com o algoritmo, uma 
boa ideia é simular o algoritmo para outros valores de x e y.
2. A linguagem Portucal
Mesmo que a linguagem natural seja muitas vezes um veículo 
eficiente para intercâmbio de informação, ela não é adequada para 
a programação de computadores, devido às suas ambiguidades 
e imprecisões. Por exemplo, embora a descrição feita na seção 
anterior do algoritmo de Euclides seja suficientemente precisa para 
que possamos compreendê-lo e simulá-lo, não temos meios para 
instruir um computador, de forma direta, a executar qualquer um de 
seus passos. De fato, as linguagens adequadas para a programação 
de computadores possuem um número finito (e em geral bastante 
restrito) de comandos e construções, além de regras precisas de 
sintaxe (as regras estruturais que todo programa deve respeitar) que 
não admitem exceções, ao contrário das possibilidades expressivas 
praticamente infinitas da linguagem natural.
Ainda que nosso objetivo não seja o aprendizado de uma linguagem 
de programação específica, precisamos nos adequar a essa realidade 
se quisermos ter alguma esperança de implementar futuramente nossos 
24
Algoritmos e Estrutura de Dados
algoritmos. Por essas razões, não vamos usar nem o Português, nem 
uma linguagem de programação corrente para descrever algoritmos. 
Nosso compromisso será o uso de uma linguagem que chamaremos 
de Portucal. O Portucal não é muito diferente das linguagens de 
programação comuns, de forma que saberemos identificar suas 
estruturas independentemente da linguagem em que já tivermos 
programado. Ele é, na verdade, projetado para ser mais simples do 
que a maioria das linguagens de programação, pois desejamos nos 
concentrar na estrutura dos algoritmos que estudaremos, e não em 
detalhes técnicos de implementação.
Por exemplo, as construções do Portucal são muito parecidas 
com as da linguagem de programação Pascal, e a tradução de 
um algoritmo descrito em Portucal para um programa em Pascal é 
quase imediata porque precisamos, na maioria das vezes, apenas 
traduzir as instruções e fazer pequenas adaptações estruturais. O 
Portucal é também bastante intuitivo: um algoritmo em Portucal pode 
ser explanado naturalmente em Português. Outra característica do 
Portucal é o uso de comandos em Português. Daí seu nome:
Portucal = Português + Pascal
A prática do projeto de algoritmos utilizando Portucal é o melhor 
método para a fixação das estruturas dessa linguagem. Como ponto 
de partida, apresentamos a seguir novamente o algoritmo de Euclides, 
agora em Portucal. Tente associá-lo com a descrição desse algoritmo 
na seção anterior:
25
Algoritmos e Estrutura de Dados
algoritmo EUCLIDES (m, n) 
x ← m
y ← n
repita
 r ← x mod y
 x ← y
 y ← r
até que r = 0
devolva x
► Calcula o máximo divisor comum entre dois 
inteiros positivos
Embora essa nova descrição possa parecer muito mais pobre, 
vemos que todos os elementos da receita de quatro passos estudada 
na seção anterior estão presentes. As flechas ← representam as 
instruções do tipo ”adote” ou “assuma o valor de”, que realizam a troca 
de valores de variáveis. O teste realizado no Passo 4 do algoritmo 
de Euclides, que induz à repetição de um trecho do algoritmo 
segundo uma condição sobre o valor da variável r, é transformado no 
comando
repita ... até que
Esse comando executa o bloco de comandos
 r ← x mod y
 x ← y
 y ← r
até que o valor da variável r seja igual a zero. Precisamos atentar 
para o fato de que o valor de r é alterado no interior desse bloco de 
comandos, e podemos provar que ele diminuirá a cada iteração – é 
por isso que o algoritmo sempre termina. O comando “mod” calcula 
o resto da divisão de x por y. Esse comando faz parte do Portucal, e 
pode, portanto, ser usado livremente.
A seguir, apresentamos uma descrição mais completa da linguagem 
Portucal. Essa descrição deve ser encarada como um manual de 
referência para consulta. Em seguida, vamos estudar outros exemplos 
de algoritmos escritos em Portucal e praticar com alguns exercícios. 
26
Algoritmos e Estrutura de Dados
Você pode passar diretamente a essa prática, e consultar a descrição 
da linguagem apenas quando julgar necessário ou quiser ter certeza 
da compreensão correta de algum conceito, instrução ou estrutura 
apresentada nos exemplos.
• Estrutura de um algoritmo
 Todo algoritmo descrito em Portucal começa com a palavra 
“algoritmo”, seguida por um nome com que o batizamos – no 
exemplo acima, “Euclides” – e uma lista de variáveis (rótulos 
para valores) que representam a instância do problema a 
ser processada pelo algoritmo – ou seja, a “entrada”, ou os 
“parâmetros” do algoritmo.
• Comentários
 É considerada uma boa prática de programação documentar 
o código com comentários que explicam seu funcionamento. 
Não fugiremos a essa regra. Todo algoritmo deve conter pelo 
menos um comentário: uma descrição do que ele faz. Mas é 
útil inserir outros comentários para explicar as passagens mais 
delicadas. Comentários não representam nenhuma modificação 
na execução do algoritmo, e podem ser inseridos em qualquer 
posição. Em Portucal, comentários começam com o símbolo ►
• Palavras reservadas
 Toda linguagem possui um determinado conjunto de comandos, 
que indicam uma ação precisa durante a execução do 
algoritmo, e não podem ser usados como nomes de variáveis. 
Tais comandos são o que chamamos de palavras reservadasda linguagem. Em Portucal, faremos a convenção de sublinhar 
as palavras reservadas (que descrevemos mais embaixo). 
• Variáveis e atribuição
 Conforme exemplificado pela descrição do algoritmo de Euclides 
na seção anterior, um algoritmo manipula dados através de 
variáveis, realizando operações e intercambiando os valores 
armazenados. Em Portucal, variáveis podem representar 
números inteiros, fracionários (com um número fixo de casas 
decimais), os valores booleanos V ou F, caracteres ou cadeias 
de caracteres, sendo que o tipo de dado poderá ser inferido do 
contexto. A atribuição do valor de uma variável x a uma variável 
y é designada por uma seta: x ← y. Atribuições podem ser mais 
27
Algoritmos e Estrutura de Dados
complexas: em geral, o lado direito da atribuição pode ser uma 
expressão qualquer. Neste caso, o resultado da expressão é 
armazenado na variável x.
• Vetores e matrizes
 Vetores e matrizes são as primeiras estruturas de dados que 
utilizaremos intensamente em nosso curso. Vamos recordar que 
um vetor é uma tabela indexada, contendo em cada posição 
um valor – um número inteiro, por exemplo. Uma matriz é uma 
tabela duplamente indexada, ou seja, de duas dimensões. Em 
Portucal, podemos representar vetores e matrizes em variáveis. 
Se A representa um vetor, e i é uma variável contendo um 
número inteiro, obtemos o valor de A na posição i através da 
construção A[i]. Se A é uma matriz, e i e j são variáveis inteiras, a 
posição (i, j) (ou seja, “linha i, coluna j”) de A pode ser acessada 
com a construção A[i, j]. Faremos a convenção de que um vetor 
começa na posição 1, e usamos a palavra reservada tamanho 
seguida do nome de um vetor para representar a dimensão 
(número de posições) desse vetor. Assim, a última posição de 
um vetor A é o número inteiro tamanho(A).
• Entrada e saída
 Em Portucal, dispomos das palavras reservadas leia e escreva 
para, respectivamente, solicitar dados ao usuário do algoritmo 
e escrever valores de variáveis em algum meio de saída. 
Ambos os comandos são seguidos por uma lista de variáveis, 
separadas por vírgula. Por exemplo, leia x, y solicita ao usuário 
a leitura de dois valores (dois números inteiros, por exemplo). 
Também podemos considerar o algoritmo como uma caixa 
preta que calcula um valor e o “envia” ao mundo externo, ao 
invés de escrevê-lo em algum meio de saída. Dito de outra 
forma, podemos considerar os algoritmos em Portucal como 
funções de linguagens de programação. Para devolver os 
dados construídos na execução do algoritmo, usamos a palavra 
reservada devolva.
• Operadores aritméticos
 Em Portucal, podemos realizar as quatro operações aritméticas 
entre números através dos símbolos + (soma), - (diferença), * 
(produto) e / (divisão). Também podemos realizar as operações 
de quociente e resto da divisão inteira com as palavras 
28
Algoritmos e Estrutura de Dados
reservadas div e mod, respectivamente. Os operandos são 
sempre valores numéricos, e o resultado de uma operação 
aritmética é um valor numérico. Parênteses podem ser usados 
livremente para facilitar a leitura de expressões aritméticas.
• Operadores relacionais
 São os operadores que permitem a comparação de valores 
numéricos. São eles: < (menor), <= (menor ou igual), > (maior), 
>= (maior ou igual), = (igual), <> (diferente). O resultado de 
uma expressão envolvendo operadores relacionais é um valor 
booleano (V ou F).
• Operadores lógicos
 Usamos os operadores E, OU, NãO para a construção de 
expressões lógicas envolvendo outras expressões lógicas ou 
variáveis booleanas. Por exemplo, (5 < 3) ou (2 * 3 = 6) é V, e 
não ((5 < 3) ou (2 * 3 = 6)) é F. Parênteses podem ser usados 
livremente para facilitar a leitura de expressões booleanas.
• Comando condicional
 Podemos desviar a execução de um algoritmo segundo 
o resultado de uma expressão lógica com o comando 
condicional
se (exp) então C1 senão C2
 Se o resultado da expressão lógica “exp” é verdadeiro, a 
execução continua no bloco de comandos C1; senão, ela 
continua no bloco de comandos C2.
• Comandos de repetição
 Vamos recordar que, no algoritmo de Euclides escrito em 
Portucal, usamos o comando de repetição
repita C até que exp
 Esse comando começa executando o bloco de comandos C, 
em seguida testa a expressão booleana exp, e continua a 
executar o mesmo bloco de comandos até que a condição se 
torne verdadeira. Em Portucal, também dispomos do comando 
de repetição
enquanto exp faça C
29
Algoritmos e Estrutura de Dados
 A primeira ação desse comando é testar a expressão booleana 
exp. Se a expressão for verdadeira, o bloco de comandos 
C é executado. Em seguida, um novo teste da expressão é 
realizado, e o bloco C é executando repetidamente enquanto o 
resultado for verdadeiro.
 Em diversas situações, é útil controlar o número de vezes em 
que um bloco de comandos deve ser executado. Essa tarefa é 
realizada pelo comando
para i ← k até n faça C
 que repete o bloco de comandos C para cada valor da variável i 
entre k e n, com incremento de uma unidade a cada iteração. Por 
outro lado, se k é maior do que n, a variável i é decrementada a 
cada execução.
• Procedimentos
 Como ocorre com procedimentos e funções em linguagens de 
programação, um algoritmo em Portucal pode ser executado no 
interior de outro algoritmo. Invoca-se um algoritmo escrevendo 
o seu nome seguido por uma lista de parâmetros entre 
parênteses. Variáveis simples são passadas por valor, ou seja, 
toda alteração dos parâmetros no interior de um algoritmo é 
invisível externamente. Por outro lado, a passagem de vetores 
e matrizes é por referência, ou seja, alterações nesses objetos 
no interior de um algoritmo são visíveis externamente.
Apresentação de algoritmos
Quem programa com frequência sabe que a leitura de um programa 
desorganizado pode ser penosa. Por isso, é importante caprichar na 
apresentação. Não fugiremos à regra. O uso de identação para a evidência 
de blocos de comando subordinados a estruturas de controle deve ser 
sistemático. Também é importante documentar nossos algoritmos, ou 
seja, escrever comentários explicando o funcionamento das partes mais 
delicadas. Finalmente, é importante descrever, também com comentários, 
o que o algoritmo faz. Observe como essas práticas são seguidas nos 
exemplos estudados nesse capítulo. Ao escrever seus algoritmos e 
programas, procure se habituar a seguí-las também.
30
Algoritmos e Estrutura de Dados
Aprenda Praticando
Ao longo dessa disciplina, escreveremos muitos algoritmos em 
Portucal. Vamos, então, nos familiarizar com essa linguagem através 
de alguns exemplos. Ao mesmo tempo, vamos discutir um pouco mais 
sobre práticas importantes no desenvolvimento de algoritmos.
Em cada exemplo, deparamo-nos com o enunciado de um 
problema. O objetivo é escrever um algoritmo que resolve o problema, 
da mesma forma que desenvolvíamos programas nas disciplinas 
introdutórias de programação.
Às vezes, é necessário ir além do projeto de um algoritmo para 
convencer que ele funciona. Em dois exemplos, vamos discutir 
rapidamente a corretude do algoritmo proposto. Dizemos que um 
algoritmo é correto se ele dá a resposta esperada para todo valor 
possível da entrada. A corretude de um algoritmo é um fato que deve 
ser demonstrado com uma prova matemática. A estratégia fundamental 
nesse tipo de questão é a utilização de certas propriedades que se 
mantêm válidas ao longo da execução, os invariantes.
Antes de ler a solução, tente resolver o problema, e compare 
seu algoritmo com o proposto. Comumente, um problema pode ser 
resolvido de diversas maneiras. Como você poderia argumentar que 
sua solução é melhor? Ou como você poderia melhorá-la?
Problema 1
Escreva um algoritmo que calcula o fatorial de um número.
Solução: Vamos recordar que o fatorial de um número n é definido 
por
n! = n x (n – 1) x ... x 2 x 1
Nosso algoritmo deve realizar uma multiplicação de n fatores. 
Para isso, uma possibilidade é utilizar o laço enquanto. Os resultadosparciais do produto são armazenados em uma variável, que após a 
última iteração é igual ao fatorial de n.
31
Algoritmos e Estrutura de Dados
algoritmo FATORIAL (n)
fat ← n
enquanto n > 1 faça
 n ← n - 1
 fat ← fat * n
devolva fat
► Calcula o fatorial de um inteiro positivo
Problema 2
Escreva um algoritmo que calcula a soma de um vetor.
A soma de um vetor A de tamanho n é definida por
A[1] + A[2] + ... + A[n]
Solução: O seguinte algoritmo resolve o problema.
algoritmo SOMA (A)
s ← 0
para i = 1 até tamanho (A) faça
 s ← s + A[i]
devolva s
► Calcula a soma de um vetor A
Como esse algoritmo é simples, podemos nos convencer 
rapidamente de que ele é correto, ou seja, sempre devolve a soma do 
vetor A. Em geral, não é tão fácil enxergar que um algoritmo é correto, 
e nesses casos precisamos de uma demonstração matemática 
baseada nos invariantes do algoritmo. É claro que o valor da variável 
s muda ao longo da execução. No entanto, a propriedade seguinte é 
sempre verdadeira ao final de cada iteração (ou seja, após a execução 
do corpo do laço para ... até). É por isso que dizemos que ela é um 
invariante (uma propriedade que nunca muda ao longo da execução):
s = A[1] + ... + A[i]
Em particular, o invariante mostra que, ao final da última iteração, 
s é igual à soma de A.
32
Algoritmos e Estrutura de Dados
Problema 3
Escreva um algoritmo que dados um vetor de n números em ordem crescente e 
um número x, determina a posição do número x, e retorna 0 caso x não apareça 
no vetor.
Solução: Temos aqui um exemplo de problema de busca. Busca é 
uma questão fundamental em Computação, e, em muitos contextos, 
é importante que possa ser realizada com eficiência – considere por 
exemplo Bancos de Dados, onde buscas são solicitadas com muita 
frequencia. Nessa disciplina, vamos estudar em breve estruturas de 
dados projetadas para que inserções, remoções e buscas em certos 
conjuntos de dados possam ser feitas com eficiência.
Quando atacamos um problema, é comum uma solução imediata 
saltar aos olhos, mas nem sempre essa solução é a melhor (em 
termos de eficiência). A solução imediata para o problema de busca em 
questão consiste em verificar todas as posições do vetor comparando 
o conteúdo de cada uma com o valor procurado x. No entanto, essa 
solução não aproveita a informação adicional de que o vetor está 
ordenado.
Com base na ordenação, o problema pode ser resolvido de forma 
muito mais eficiente. Veremos no próximo capítulo noções sobre 
eficiência de algoritmos. Mas uma experiência que realizaremos ao 
final desse capítulo dará indícios de que as execuções do algoritmo 
que vamos descrever são menos “trabalhosas” do que as do algoritmo 
exaustivo.
Esse algoritmo se chama busca binária, e segue uma estratégia 
conhecida em Ciência da Computação como divisão e conquista. A 
idéia é dividir o problema em partes menores, ou subproblemas, e 
atacá-las em separado. Esses subproblemas, por sua vez, são casos 
menores do mesmo problema, e podem então ser resolvidos com a 
mesma estratégia, ou melhor, com o mesmo algoritmo: dividindo-os 
em problemas ainda menores.
A busca binária começa determinando o índice que aponta para 
a metade do vetor. Evidentemente, o valor procurado está ou nessa 
posição, ou na metade à esquerda do vetor, ou na metade à direita. 
Agora, chegamos à observação crucial para o projeto desse algoritmo: 
a comparação do valor procurado com o valor nessa posição mostra 
em qual metade do vetor a busca deve prosseguir. Assim, metade do 
vetor pode ser desprezada, e a busca continua na outra metade.É 
Atenção
Dizemos que 
um vetor A está 
ordenado, ou em 
ordem crescente, 
se, para todo 
índice i entre 1 e 
o tamanho de A 
menos 1, temos 
A[i] ≤ A[i + 1]. 
Como se 
define ordem 
decrescente?
Atenção
Origem do 
termo “divisão e 
conquista”
O termo “divisão 
e conquista” era 
usado no exército 
de Napoleão 
para designar 
a estratégia 
de dividir o 
exército inimigo 
em exércitos 
menores e mais 
fáceis de derrotar.
33
Algoritmos e Estrutura de Dados
aqui que a ordem crescente é utilizada: em um vetor que não está 
ordenado, não é possível concluir em qual das metades o número 
poderia estar.
De modo geral, a cada iteração do algoritmo uma região do vetor 
é analisada. Essa região é determinada por duas variáveis, esq (o 
limite inferior) e dir (o limite superior). Apenas uma dessas variáveis 
é atualizada, de acordo com a comparação do valor procurado com o 
valor na posição intermediária dessa região.
Vamos notar que na documentação do algoritmo especificamos 
que o vetor A fornecido na entrada deve estar em ordem crescente. 
Como mencionamos anteriormente, é importante especificar o que o 
algoritmo faz, e em particular, o que ele recebe, e o que ele devolve. 
O algoritmo não promete que encontra x para qualquer vetor possível. 
Mas promete que o encontra para qualquer vetor ordenado.
algoritmo BUSCA-BINÁRIA (A, x) ► Recebe um vetor A de inteiros em ordem
► crescente e um inteiro x, devolve um índice
► i tal que A[i] = x ou 0 se um tal índice
► não existe.
esq ← 1
dir ← tamanho (A) ► Supomos que A tem pelo menos
► um elemento, ou seja, dir >= 1
repita
 meio ← (esq + dir) div 2
 se x > A[meio] então
 esq ← meio + 1
 senão
 dir ← meio – 1
até que (A[meio] = x) OU (esq > dir)
se A[meio] = x então
 devolva meio
senão
 devolva 0
34
Algoritmos e Estrutura de Dados
A compreensão do busca-binária fica muito mais fácil se realizamos 
algumas simulações. Consideremos por exemplo o seguinte vetor, 
indexado de 1 a 11:
Índice 1 2 3 4 5 6 7 8 9 10 11
Valor 8 23 37 44 50 57 57 86 91 102 104
Busquemos o valor 86. O índice que aponta para o meio do vetor 
é
(esq + dir) div 2 = (1 + 11) div 2 = 6
O valor nessa posição é 57, que é menor que 86. Dessa forma, 
a parte esquerda do vetor pode ser desprezada (área mostrada em 
cinza claro):
Índice 1 2 3 4 5 6 7 8 9 10 11
Valor 8 23 37 44 50 57 57 86 91 102 104
A variável esq é então atualizada para apontar o início da segunda 
metade. Na próxima iteração, o algoritmo considera a região do vetor 
determinada por
esq = 7, dir = 11
cujo meio é o índice 9. O valor na posição 9 é 91, maior do que 86. 
Então, a metade direita da região entre 7 e 11 é desprezada (área 
mostrada em preto), e o algoritmo atualiza dir para 8:
Índice 1 2 3 4 5 6 7 8 9 10 11
Valor 8 23 37 44 50 57 57 86 91 102 104
O meio dessa região é o índice 7 (o quociente da divisão de 7 + 8 
por dois), que indica o valor 57. Esse valor é menor do que 86, então 
esq passa a valer 8 e a região à esquerda (área mostrado em cinza 
escuro) é descartada. Neste caso, a região descartada se resume ao 
índice 7 do vetor. Finalmente, ambas variáveis valem 8, e o trecho a 
pesquisar contém apenas um elemento:
Índice 1 2 3 4 5 6 7 8 9 10 11
Valor 8 23 37 44 50 57 57 86 91 102 104
Aqui o algoritmo encontra o valor e devolve o índice 8.
Atenção
Vamos recordar 
que na linguagem 
Portucal os 
vetores são 
indexados a 
partir do índice 
1. A definição da 
linguagem, na 
seção anterior, 
tem mais 
informações 
sobre vetores.
35
Algoritmos e Estrutura de Dados
Como provar que o algoritmo é correto? Ou seja, como provar 
que o algoritmo sempre encontra um índice que aponta para o 
valor procurado, se esse valor aparece no vetor, e devolve 0 caso 
contrário?
Como fizemos no exemplo anterior, a demonstração baseia-se em 
invariantes. O invariante seguinte permanece verdadeiro no início de 
cada iteração do laço repita:
se x ocorre em A, então A[esq] ≤ x ≤ A[dir]
Em outras palavras, se o valor procurado (x) existir no vetor A, o 
índice referente a sua posição estará sempre entre a primeira posição 
da região considerada e a última. Contudo, não devemos acreditar 
nessa propriedade gratuitamente: é preciso justificar, a partir das 
operações realizadas pelo algoritmo, que ela continua verdadeira 
sempre que os valores de esq e dir são alterados.
Para completar essa análise de corretude, precisamos de outra 
propriedade:
a cada iteração,esq – dir diminui.
Essencialmente, ela mostra que o algoritmo termina. A combinação 
de ambas permite concluir que o algoritmo sempre dá a resposta 
esperada.
Problema 4
Escreva um algoritmo que recebe um vetor de números inteiros, positivos ou 
negativos, e devolve um subconjunto de índices desse vetor tal que a soma 
dos números nesses índices seja igual a zero. Se um tal conjunto não existe, o 
algoritmo deve devolver o conjunto vazio.
Por exemplo, para o vetor
A = -4, -1, 6, -1, 2
o subconjunto de índices {2, 4, 5} produz uma soma igual a zero:
A[2] + A[4] + A[5] = (-1) + (-1) + 2 = 0
Neste caso, o algoritmo pode devolver o subconjunto {2, 4, 5}, ou 
qualquer outro que produza soma zero (outra possibilidade é o 
subconjunto {1, 2, 3, 4}). Para o vetor
B = 1, -2, 3, 4
nenhum subconjunto de índices resulta em zero. Neste caso, o 
algoritmo responde {}.
Atenção
Falaremos um 
pouco da Teoria 
da Complexidade 
no próximo 
capítulo.
36
Algoritmos e Estrutura de Dados
Solução: Esse problema é famoso, porque tem uma importância 
particular numa área da Ciência da Computação chamada “Teoria da 
Complexidade”. Ele é conhecido como “Soma de Subconjuntos”, do 
inglês Subset Sum.
Nossa solução para o Soma de Subconjuntos será uma busca 
exaustiva: vamos analisar todos os subconjuntos de índices do vetor, 
e para cada subconjunto, testar se a soma dos números indicados 
pelos índices é igual a 0. Por exemplo, se nosso vetor tem tamanho 
3 (e portanto é indexado de 1 a 3), nosso algoritmo verifica os 
subconjuntos
{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
Talvez você fique com a impressão de que essa solução não é 
muito eficiente, e isso é verdade – se o vetor for grande, há muitos 
subconjuntos para testar. Por outro lado, todas as soluções conhecidas 
para esse problema têm o mesmo defeito, ou seja, nenhum algoritmo 
eficiente é conhecido. Vamos discutir melhor esse fato no último 
capítulo desse volume.
Nosso algoritmo tem duas tarefas básicas, enumerar os 
subconjuntos de índices do vetor, e testar a soma para cada 
subconjunto. Para realizar a primeira tarefa, nossa estratégia será 
gerar todos os números binários de n dígitos, onde n é o tamanho 
do vetor. Cada número binário representa um subconjunto de índices: 
exatamente aqueles correspondentes às posições do número binário 
onde o dígito é 1. Por exemplo, se nosso vetor tem tamanho 5, o 
número binário
01101
(lido da esquerda para a direita) representa o subconjunto de índices
{2, 3, 5}.
A geração dos números binários, por sua vez, pode ser feita 
naturalmente em ordem crescente do valor representado pelo número 
– no presente exemplo, de 00000 até 11111. Ou seja, a geração do 
próximo número binário consiste em somar uma unidade (um dígito 
binário) ao número atual.
Para simplificar o entendimento do algoritmo, vamos utilizar um 
algoritmo auxiliar, chamado SOMA-UM, que realiza a soma de uma 
unidade a um número binário. Também vamos escrever esse número 
37
Algoritmos e Estrutura de Dados
em um vetor, B, armazenando cada dígito em uma posição. Por 
exemplo, o vetor
B = 1, 0, 0, 1
armazena o numero binário 1001, cuja valor é 9. Após a execução de 
SOMA-UM, esse vetor representa o número 1010, cujo valor é 10.
Para entender melhor como funciona o algoritmo auxiliar SOMA-
UM, observe a Tabela 1, que também exemplifica a representação de 
números binários em um vetor. Em seguida, apresentamos o algoritmo 
SOMA-SUBCONJUNTOS:
Valor Binário Vetor B Subconjunto 
representado
Cada subconjunto de 
índices que o algoritmo 
SOMA-SUBCONJUNTOS 
considera é representado 
por um número binário. 
O algoritmo SOMA-
UM é responsável por 
incrementar (somar um) a 
esses números. 
Cada número binário 
é representado no 
vetor B, um dígito por 
posição. O algoritmo 
SOMA-UM recebe 
um vetor com esse, e 
modifica-o, de forma 
a somar um ao valor 
representado.
O algoritmo SOMA-
SUBCONJUNTOS 
usa o vetor B para 
representar um 
subconjunto de índices: 
exatamente os índices 
cujos valores em B são 
iguais a 1
00000 B[1]=0 B[2]=0 B[3]=0 
B[4]=0 B[5]=0
00001 B[1]=0 B[2]=0 B[3]=0 
B[4]=0 B[5]=1
5
00010 B[1]=0 B[2]=0 B[3]=0 
B[4]=1 B[5]=0
4
00011 B[1]=0 B[2]=0 B[3]=0 
B[4]=1 B[5]=1
4, 5
00100 B[1]=0 B[2]=0 B[3]=1 
B[4]=0 B[5]=0
3
00101 B[1]=0 B[2]=0 B[3]=1 
B[4]=0 B[5]=1
3, 5
00110 B[1]=0 B[2]=0 B[3]=1 
B[4]=1 B[5]=0
3, 4
00111 B[1]=0 B[2]=0 B[3]=1 
B[4]=1 B[5]=1
3, 4, 5
Tabela 1: Representação de subconjuntos no algoritmo SOMA-SUBCONJUNTOS
38
Algoritmos e Estrutura de Dados
algoritmo SOMA-SUBCONJUNTOS(A) ► Decide se um vetor de inteiros A tem
► um subconjunto de índices tal que
► a soma dos números indicados é 0.
n ← tamanho(A)
para i ← 1 até n faça
 B[i] ← 0
 V[i] ← 0
► Inicialização de um vetor, B, que
► representa números binários e de um
► vetor V que representa o conjunto vazio 
repita
 soma ← 0
 m ← 0 ► Ao final da iteração, m contém o
► número de dígitos iguais a 1 no vetor B 
 SOMA-UM (B) ► Armazena em B o próximo número
► binário, em ordem de valor
para i ← 1 até n faça 
 se B[i] = 1 então
 soma ← soma + A[i]
 m ← m + 1
até que (soma = 0) OU (m = n) ► O laço termina quando um subconjunto 
► é encontrado, ou quando todos os
► subconjuntos já foram analisados
se soma = 0 então
 devolva B ► Devolve o subconjunto de índices
► encontrado
senão
 devolva V ► Devolve o conjunto vazio
Conheça Mais
A descrição do algoritmo de Euclides na Seção 1 e a definição 
da linguagem Portucal foram inspiradas no livro Aspectos Teóricos 
da Computação, dos autores Cláudio L. Lucchesi, Imre Simon, 
Istvan Simon, Janos Simon e Towasz Kowaltowski. Trata-se de 
39
Algoritmos e Estrutura de Dados
uma excelente referência em Língua Portuguesa sobre Teoria da 
Computação, e a primeira parte, sobre programação de computadores, 
contem muitos fatos sobre algoritmos que não vamos tratar em nosso 
curso. Por ser antigo, o livro encontra-se esgotado, mas os autores 
disponibilizam gratuitamente na Internet uma versão digitalizada:
 http://www.ime.usp.br/~is/atc/index.html
Nessa altura da disciplina, é uma excelente ideia resolver exercícios 
de desenvolvimento de algoritmos usando a linguagem Portucal. Por 
isso, ao final do capítulo, propomos uma atividade prática sobre o 
assunto. No entanto, você pode buscar outros problemas, e discutir 
suas soluções com seus colegas. Um bom repositório de problemas 
é o site
 http://www.ime.usp.br/~macmulti/
Você sabia?
Desenvolvimento de algoritmos e programação de computadores 
são atividades delicadas, que exigem muita atenção a todos os 
detalhes. É muito comum cometermos erros - os famosos bugs, que 
às vezes são muito sutis e de difícil identificação. Infelizmente, mesmo 
erros mínimos podem comprometer drasticamente a execução e 
produzir resultados absurdos.
A busca-binária é um exemplo de algoritmo simples cuja 
programação exige atenção redobrada. A experiência mostra que 
muitos programadores iniciantes, e às vezes até programadores 
avançados, cometem erros ao implementá-lo.
Por exemplo, uma versão da busca-binária semelhante à proposta 
neste capítulo foi implementada na biblioteca padrão da linguagem 
java e utilizada com sucesso por milhares de programadores por 
alguns anos. Essa versão teve de ser modificada após um relatório de 
erro, onde se verificou que a operação
meio ← (esq + dir) div 2
pode “estourar” (ocorrência de um “overflow”, no jargão em inglês) se 
a soma esq + dir for maior do que o limite superior de representação 
de números inteiros da linguagem.
40
Algoritmos e Estrutura de Dados
Essa operação foi corrigida para
meio ← esq + ((dir - esq) div 2),
que resolve o problema.
Do nosso ponto de vista, o algoritmo é correto, pois não estamos 
considerando detalhes de implementação. Cabe notar, no entanto, 
que a “tradução” de Portucal para uma linguagem de programação 
real pode exigir certos cuidados além da simples substituição de 
comandos.
Atividades e Orientações de Estudo
Nessa atividade prática,vamos elaborar três algoritmos em 
Portucal, e em seguida realizar uma implementação numa linguagem 
de programação.
As implementações devem ser compiladas e testadas 
intensivamente, conforme descrevemos no enunciado do Exercício 4. 
Entre em acordo com o seu professor a respeito da linguagem a ser 
utilizada.
Exercício 1
Escreva um algoritmo que testa se um vetor está em ordem crescente.
Exercício 2
Escreva um algoritmo que recebe um vetor de números inteiros e um número 
inteiro x, determina uma posição contendo x, e retorna essa posição ou 0 caso x 
não apareça no vetor.
Nesse novo exercício de busca, você não pode supor que o vetor 
está ordenado. Assim, não resta alternativa senão a realização de 
uma busca sequencial.
Exercício 3
Escreva o algoritmo soma-um usado por busca-binária. O soma-um recebe 
um vetor B contendo zeros e uns, interpretado como um número binário que 
representa um número natural x (sendo a posição menos significativa a mais à 
esquerda), e modifica o vetor de forma que o valor representado seja x + 1.
Para resolver esse exercício, precisamos recordar que a passagem 
41
Algoritmos e Estrutura de Dados
de parâmetros em Portucal é por referência quando o parâmetro é um 
vetor. Ou seja, o seu algoritmo recebe um vetor B, mas não devolve 
nada (veja mais detalhes na descrição da linguagem). A alteração 
do vetor B será visível externamente. Além disso, você deve antes 
de projetar seu algoritmo fazer uma decisão de projeto: se todas as 
posições do vetor B são iguais a 1, ou seja, o maior número possível é 
representado, como o algoritmo deve se comportar? Documente (com 
um comentário) essa sua decisão, de forma a tornar o funcionamento 
do seu algoritmo bastante claro para um usuário.
Exercício 4
Implemente o algoritmo busca-binária e o algoritmo que você projetou para 
resolver o Exercício 2 em alguma linguagem de programação. Execute ambos os 
algoritmos para diversos vetores ordenados, variando o tamanho desses vetores 
e a posição do número procurado. O que você observa?
Vamos em seguida realizar uma atividade de interação.
Primeiro, busque encontrar os invariantes importantes para a 
demonstração da corretude dos algoritmos que você projetou para os 
dois primeiros exercícios. Discuta-os com seus colegas e tutores no 
ambiente.
Em seguida, discuta no ambiente o resultado do teste de sua 
implementação. Tente chegar a uma conclusão sobre a execução 
de ambos os algoritmos, especialmente para vetores muito grandes. 
Algum deles é sempre mais rápido? Caso positivo, tente descobrir a 
razão juntamente com seus colegas.
Vamos revisar?
Neste capítulo, introduzimos uma linguagem para representação de 
algoritmos, que chamamos de Portucal. Além do aprendizado dessa 
linguagem, discutimos alguns exemplos de algoritmos, consideramos 
a importância da prática da documentação, e aprendemos que 
a corretude de um algoritmo pode ser demonstrada através da 
identificação de invariantes do mesmo.
42
Algoritmos e Estrutura de Dados
Capítulo 3 – Algoritmos 
recursivos
Vamos conversar sobre o assunto?
Talvez você já tenha ouvido falar de definições recursivas em 
Matemática, ou então já estudou alguma demonstração baseada 
no princípio da indução matemática. Em ambos os casos, a ideia 
subjacente é a possibilidade de definir um objeto através de uma 
versão “menor” do mesmo objeto.
Veremos, neste capítulo, que também é possível definir algoritmos 
que fazem uso de si mesmos durante a execução. Essa técnica, 
chamada recursão, é fundamental em programação de computadores, 
além de ser uma ferramenta poderosa para o desenvolvimento de 
algoritmos. De fato, o uso de recursão pode conduzir a algoritmos 
notavelmente simples e elegantes, especialmente se o problema 
em questão possuir uma estrutura recursiva. Vamos estudar alguns 
exemplos desses algoritmos, e compará-los com outros algoritmos 
que não utilizam recursão – os algoritmos iterativos.
Por outro lado, veremos também que a recursão não pode ser 
utilizada de maneira indiscriminada: em certas situações, um algoritmo 
iterativo é a melhor solução. 
1. O conceito de recursão
Quem nunca viu uma imagem que contém uma cópia de si própria? 
Tais imagens são chamadas de recursivas.
43
Algoritmos e Estrutura de Dados
Muitos conceitos em Matemática têm uma estrutura recursiva. 
Por exemplo, os fractais são curvas que contêm cópias menores 
semelhantes a si mesmas. Abaixo, vemos as primeiras etapas da 
construção de um fractal conhecido como “curva de Koch”.
De forma geral, nas definições recursivas de objetos matemáticos 
desejamos definir um objeto de tamanho n, onde n é um número 
natural. Se n é pequeno, definimo-lo diretamente, de forma explícita. 
Se n é grande, definimo-lo utilizando a mesma definição, mas para 
valores menores de n. 
Um exemplo é a definição de fatorial:
 n! = 0 para n = 0 ou n = 1
 n x (n – 1)! para n > 1
Essa definição pode ser imediatamente transformada num 
algoritmo que chama a si próprio para o cálculo do fatorial. Trata-se 
de um algoritmo recursivo.
algoritmo FATORIAL-REC(n) ► Calcula o fatorial de um inteiro positivo
se n <= 1 então
 devolva 1
senão
 devolva n * FATORIAL-REC(n – 1)
Como se convencer de que o algoritmo funciona? Discutiremos 
essa questão ao longo desse capítulo. Em linhas gerais, é preciso 
raciocinar de maneira indutiva. Ou ainda, é preciso confiar que o 
algoritmo resolve corretamente o problema para n – 1.
Vimos no capítulo anterior um algoritmo para o cálculo do fatorial 
que não utiliza recursão. Dizemos que esse algoritmo é iterativo, 
devido ao uso de uma estrutura repetitiva que realiza uma sequência 
de iterações. O algoritmo FATORIAL-REC também realiza todas as 
multiplicações necessárias para o cálculo de n!, mas essas operações 
estão “espalhadas” em chamadas distintas do algoritmo.
Lembrete
verbete recursão
Para definição, 
veja recursão
Lembrete
“Para fazer um 
procedimento 
recursivo é 
preciso ter fé.”
Siang Wun Song
44
Algoritmos e Estrutura de Dados
Os números de Fibonacci são outro bom exemplo de definição 
recursiva. Esses números formam uma sequência infinita de números 
naturais,
f0, f1, f2, ...
que são definidos como segue:
 f0 = 0
 f1 = 1
 fn = fn-1 + fn-2 para n > 1
Ou seja, para índices pequenos (0 ou 1), o número de Fibonacci é 
definido diretamente. Para todo índice n grande, o número de Fibonacci 
fn é a soma de dois números de Fibonacci de índices menores. Os 
primeiros números de Fibonacci são
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
Como no exemplo anterior, a definição recursiva dos números de 
Fibonacci se transforma naturalmente num algoritmo recursivo que 
recebe um natural n e devolve fn.
algoritmo FIBONACCI(n) ► Calcula o n-ésimo número de Fibonacci
se n = 0 então
 devolva 0
senão
 se n = 1 então
 devolva 1
 senão
 devolva FIBONACCI(n – 1) + FIBONACCI(n - 2)
É instrutivo simular as chamadas recursivas desse algoritmo. Por 
exemplo, para n = 5, o algoritmo executa fibonacci(4) e fibonacci(3), 
esperando o resultado dessas execucções para calcular o falor de 
f5. Por sua vez,fibonacci(4) executa fibonacci(3) e fibonacci(2), 
enquanto que fibonacci(3) executa fibonacci(2) e fibonacci(1), 
e assim por diante. Tente desenhar essas chamadas recursivas de 
forma hierárquica, usando uma estrutura de árvore, e anote os valores 
calculados em cada chamada.
Atenção
Fibonacci
Os números de 
Fibonacci são 
assim batizados 
em homenagem 
ao matemático 
italiano Leonardo 
de Pisa (1170 - 
1250), também 
chamado de 
Fibonacci devido 
à contração filius 
Bonaccio, “filho 
de Bonaccio”. 
Fibonacci 
introduziu essa 
sequencia na 
Europa ocidental 
em sua obra Liber 
Abaci. Mas eles já 
eram conhecidos 
na Matemática 
hindu.
45
Algoritmos e Estrutura de Dados
À primeira vista, pode parecer estranho que seja possível executar 
algoritmos recursivos em computadores. Uma reflexão sobre 
organização de computadores espanta todo mistério.
Sempre que uma função ou procedimento é executado,o 
computador armazena na memória o estado atual do processamento, 
ou seja, os valores de todas as variáveis. Ao término da execução do 
procedimento, esses valores são recuperados, e a execução continua 
na instrução seguinte.
Um procedimento recursivo é um procedimento legítimo, como 
outro qualquer. Sua particularidade é que ele chama a si próprio, 
potencialmente muitas vezes. Para cada chamada, o estado da 
execução é armazenado na memória, compondo uma estrutura de 
pilha de estados de memória.
Quando o caso básico da recursão é atingido, essas execuções 
encaixadas terminam sucessivamente, e os estados de memória 
correspondentes são desempilhados. O resultado a ser calculado na 
primeira chamada do algoritmo depende dos resultados calculados no 
momento em que esses estados de memória são desempilhados.
Algoritmos recursivos são intimamente relacionados com indução 
matemática. Vamos recordar que indução é uma técnica de prova que 
permite estabelecer a validade de uma propriedade para todo número 
natural. Por exemplo, vamos usar indução para demonstrar que para 
todo número natural n é verdade que
1 + 2 + ... + n = n(n + 1) / 2
A estratégia de uma prova por indução é semelhante à de um 
algoritmo recursivo: se n é pequeno (base da indução), resolva o 
problema explicitamente, e se n é grande, use a hipótese de que a 
propriedade é verdadeira para valores menores de n (hipótese de 
indução):
• n = 1: a propriedade é verdadeira, pois neste caso n(n + 1) / 2 = 
1.
• n > 1: vamos dividir a soma em duas partes, 1 + 2 + ... + (n – 1) 
e n. Pela hipótese de indução, a primeira parte é igual a (n - 1)n / 
2. A soma total é igual a (n - 1)n / 2 + n, que é igual a n(n + 1) / 2. 
A propriedade está assim demonstrada.
Provas indutivas também são úteis para demonstrar a corretude 
46
Algoritmos e Estrutura de Dados
de algoritmos recursivos. A base da indução corresponde aos valores 
calculados explicitamente pelo algoritmo, e o passo de indução usa o 
fato de que o algoritmo dá a resposta correta para valores menores 
do considerado.
Vamos concluir essa seção analisando uma questão. Vimos no 
exemplo do fatorial dois algoritmos para resolver o mesmo problema, 
um recursivo e um iterativo. É verdade que para todo algoritmo 
recursivo podemos construir um algoritmo iterativo que resolve o 
mesmo problema? A resposta é sim. Uma estratégia que sempre 
funciona é simular a execução da pilha de recursão explicitamente, 
com o uso de variáveis auxiliares. No entanto, essa simulação produz 
em alguns casos algoritmos iterativos muito complicados.
2. Deve-se sempre usar recursão?
Recursão é uma ferramenta poderosa, que se utilizada corretamente 
leva a algoritmos simples e elegantes. No entanto, deve-se utilizar 
recursão sistematicamente sempre que o problema considerado tem 
uma estrutura recursiva?
A resposta é não, e a razão principal é que o número de chamadas 
recursivas do algoritmo pode ser proibitivamente grande. Veremos, no 
próximo capítulo, noções de análise de algoritmo. Mas podemos desde 
já guardar a lição de que se o algoritmo executa uma quantidade de 
operações proporcional a uma função de crescimento muito lento, 
como a função exponencial, então esse algoritmo não será útil na 
prática.
 Esse é o caso do algoritmo recursivo que apresentamos para o 
cálculo dos números de Fibonacci. Ao simular a execução do algoritmo, 
percebemos que o número de chamadas recursivas é exponencial. 
Neste caso, o algoritmo iterativo a seguir é muito mais eficiente:
47
Algoritmos e Estrutura de Dados
algoritmo FIBONACCI-ITERATIVO(n) ► Calcula o n-ésimo número de 
Fibonacci
a ← 0
b ← 1
para i ← 2 até n faça
 f ← a + b
 a ← b
 b ← f
devolva b
Outra razão para cautela antes do uso de algoritmos recursivos 
é o fato de que as chamadas do algoritmo podem implicar no 
empilhamento de grandes volumes de informação na memória 
(recorde a discussão sobre a pilha de execução de um algoritmo 
recursivo feita anteriormente).
No entanto, também não é verdade que algoritmos recursivos são 
inerentemente ineficientes. A escolha entre um algoritmo recursivo e 
um iterativo é assim uma decisão importante de projeto, que depende 
de uma análise cuidadosa do problema, e exige, naturalmente, alguma 
experiência que só adquirimos através da prática.
Conheça Mais
Se você não está familiarizado com demonstrações por indução 
matemática, esse é um bom momento para se aprofundar. Voltaremos 
a usar indução nessa disciplina para demonstrar fatos sobre outros 
algoritmos. Procure realizar a demonstração de algumas propriedades 
sobre números inteiros por indução. Um bom repositório de problemas 
é o Capítulo 2 do livro Problems on Algorithms de Ian Parberry e 
William Gasarch que está disponível on-line para uso livre:
 http://www.eng.unt.edu/ian/books/free/poa.pdf
Para se aprofundar no estudo de algoritmos recursivos, uma boa 
referência é o livro
48
Algoritmos e Estrutura de Dados
 WIRTH, N. Algoritmos e Estruturas de Dados. Rio de Janeiro: 
Ed. Prentice Hall do Brasil, 2002.
Atividades e Orientações de Estudo
Vamos realizar duas atividades práticas.
Na primeira, vamos desenvolver uma versão recursiva do algoritmo 
que busca um valor em um vetor (não necessariamente ordenado). 
Na versão iterativa do algoritmo que você desenvolveu no capítulo 
precedente, o algoritmo recebe duas entradas, o vetor e o número a 
ser localizado. Neste exercício, vamos observar que a versão recursiva 
necessita de um parâmetro adicional, que indica o início da região do 
vetor onde a busca será efetuada. Observe que esse algoritmo é mais 
geral do que o outro, e responda: como se enuncia o problema mais 
geral que esse algoritmo resolve?
Na segunda atividade, o objetivo é buscar uma explicação para a 
ineficiência da versão recursiva do algoritmo que calcula o n-ésimo 
número de Fibonacci.
Implemente ambos os algoritmos numa linguagem de programação 
que será determinada pelo professor. Também inclua, na versão 
recursiva, a impressão do valor do parâmetro recebido pelo vetor. Ou 
seja, cada vez que uma chamada recursiva é executada, o algoritmo 
imprime o valor de n. Execute ambos os algoritmos para diversos 
valores de n, e compare o tempo de execução.
Em seguida, verifique as mensagens impressas pela versão 
recursiva. O que você conclui? Para ajudar, é útil refletir também sobre 
a árvore de execução do algoritmo cujo desenho sugerimos. Discuta 
suas conclusões com seus colegas no ambiente.
Vamos revisar?
Neste capítulo, estudamos o conceito de recursão e analisamos 
alguns algoritmos recursivos. Vimos que recursão é um recurso 
poderoso e particularmente útil para o desenvolvimento de algoritmos 
49
Algoritmos e Estrutura de Dados
para problemas de estrutura recursiva. Também aprendemos que 
recursão deve ser utilizada com cautela, pois em determinadas 
situações o número de vezes que o algoritmo chama a si mesmo pode 
ser explosivo.
50
Algoritmos e Estrutura de Dados
Capítulo 4 – Análise de um 
algoritmo
Vamos conversar sobre o assunto?
Neste último capítulo, vamos discutir o conceito de eficiência de 
um algoritmo.
Às vezes, esperamos muito tempo diante do computador o término 
da execução de alguma operação. Nessas situações, tendemos a 
concluir que nosso equipamento não é tão bom. Temos a impressão 
de que o problema se resolveria com a substituição do processador 
ou um aumento de memória. Pode ser verdade. A evolução e 
aumento de complexidade dos sistemas operacionais, por exemplo, 
exigirá naturalmente tecnologias mais eficazes para um desempenho 
satisfatório. Por outro lado, o problema nem sempre está associado à 
tecnologia disponível.
De nosso estudo nos capítulos anteriores, podemos concluir que 
qualquer serviço disponível num computador depende de um ou 
mais algoritmos – alguns simples, outros muito delicados. Também 
consideramos que a execução de um algoritmo, para qualquer entrada, 
deve ocorrer em tempo finito – condição que faz parte da definição 
de algoritmo. Não