Recursividade

Nesse post você encontra vários exercícios sobre recursividade, uma ferramenta essencial das linguagens de programação que permite a realização várias ações que são extremamente custosas logicamente se fosse feito da forma iterativa.

Atenção: a recursão básica é bem fácil de compreender, no entanto, os exercícios e suas aplicações podem se tornar muito complicadas. Recomendo que antes de começar a resolver os exercícios você faça uma leitura em um material de apoio como esse do IME-USP.

Esses exercícios fazem parte de uma sequência de conteúdos gratuitos disponibilizados por nosso website. Clique aqui para saber mais.

1) Escreva um algoritmo iterativo para avaliar a * b usando a adição, onde a e b são inteiros não-negativos.

2) Imagine a como um vetor de inteiros. Apresente algoritmos recursivos para calcular: 

a) O elemento máximo do vetor; 
b) O elemento mínimo do vetor;
c) a soma dos elementos do vetor;
d) o produto dos elementos do vetor;
e)  a média dos elementos do vetor.

3) Crie um programa capaz de realizar as operações de cada um dos itens abaixo, usando ambas as definições iterativa e recursiva:

a) 6! 
b) 9! 
c) 100 * 3 
d) 6* 4 
e) fib(10) 
f) fib(10)

4) Suponha que um vetor de dez inteiros contenha os elementos: 1, 3, 7, 15, 21, 36, 78, 95, 106. Crie um programa que implementa a busca binária recursiva para encontrar qualquer valor do vetor.

5) Escreva uma versão iterativa do algoritmo de busca binária. (Dica: Modifique diretamente os valores de low e high.)