Lista de exercícios de recursão

Lista de Exercícios sobre Recursividade, Ordenação e Busca.

1) Execute os exemplos abaixo e mostre o que será impresso:

a) int G = 10;

void main() {

loop(10);

}

void loop(int n) {

if (G-- > 0) loop(--n);

printf(“%d ”, (n+G)); }

}

b) int G = 5;

void main() {

loop(7);

}

void loop(int n) {

if (--G > 0) loop(n--);

printf(“%d ”, (n+G)); }

}

2) Qual o retorno do método Abaixo? Para x = 7

int fib(int x){

if ((x == 1) || (x == 0)) return 1;

else return (fib(--x) + fib(--x));

}

3) Implemente os algoritmos de Busca por Interpolação e por Interpolação Robusca e

compare-os com o algoritmo de busca binária. (LIFE).

4) Implemente o algoritmo de busca binária para vetor e lista simplesmente encadeada

iterativa e recursiva.

5) Refaça o algoritmo de busca binária para que o mesmo mostre passo a passo que

elementos foram eliminados da comparação.

6) Implemente o algoritmo da Bolha “levando o menor elemento para primeira posição o

segundo menor para segunda posição e assim por diante. Mostre passo a passo cada

iteração.

7) Implemente o Algoritmo da Bolha Bidirecional. Ou seja, Leve ao mesmo tempo os

elementos maiores para últimas posições e os menores para primeiras

8) Implemente um método para inserir ordenado em um vetor. Em seguida adapte para

uma LSE.

9) Faça uma comparação de tempo entre os três algoritmos de ordenação bolha, quick e

selection usando instâncias de 10, 50 e 100 elementos.

10) Faça um algoritmo que mostre passo a passo a ordenação da bolha, ou seja, mostre cada

troca.

11) Dentro os três algoritmos quadráticos estudados, mostre qual o melhor se o vetor estiver

ordenado, aleatório, quase ordenado, ordem inversa.

12) Mostre passo a passo como seria a ordenação do vetor {4, 2, 1, 3, 6, 5, 8, 7} usando

bolha, inserção, seleção, quick sort para v={5,3,1}.

13)