CI067 - Oficina de Computação
Exercícios # 09
2º semestre 2013

Recursividade

PARTE I - Atividades em Laboratório

(potencia)Escreva uma função recursiva para o cálculo da potência de um número inteiro. Assuma potência inteira positiva e, em uma segunda versão, considere também potências negativas. DICA: $x^n = x * x^{(n-1)}$

(mdceuclides)Um algoritmo conhecido para calcular o maior divisor comum de dois inteiros $m$ e $n$ é o Algoritmo de Euclides, definida como segue: $$mdc(m,n) = mdc(n,m) ~~se~~ n > m;$$ $$mdc(m,n) = n ~~se~~ (n \le m) ~~e~~ m~~mod~~n = 0;$$ $$mdc(m,n) = mdc(n,m~~mod~~n) ~~caso~contrario.$$ Construa a função recursiva que implementa este algoritmo, bem como um programa conveniente de teste.

(recursao)Escreva a versão não-recursiva das funções f() e g() abaixo.

/* Compilar com "gcc -g -pg"
 * Apos execucao, usar "gprof a.out gmon.out"
 */

#include <stdio.h>
#include <stdlib.h>

int f(int i)
{
  if (i > 1)
    return (i + f(i-1));
  else
    return (1);

}

int g(int i)
{
  if ( 0 <= i && i < 2)
    return (i);
  else
    return (g(i-1) + g(i-2));
}


 main(int argc, char *argv[])
{
   long int i, limite;

   if (argc > 1)
      limite=atol(argv[1]);
   else
      limite=20;

   printf ("Limite = %lu\n", limite);
   printf ("Aguarde ..... \n");

   for (i=limite; i>0; i--) {
     printf ("\tF(%lu) = %lu\n", i, f(i));
     printf ("\tG(%lu) = %lu\n", i+2, g(i+2));
   }
   printf ("Acabou !!!!!\n");
}

PARTE II - Exercícios

(buscarec) Escreva um algoritmo recursivo para resolver o problema de Busca em Vetor: Dada uma instância $(x, v, a, b)$, a resposta é um índice na ``primeira metade'' de $v$ se $x$ ocorre na ``primeira metade'' de $v$. Caso contrário, a resposta é a resposta do problema ``reduzido à primeira metade de v''.

(somarec)Implemente recursivamente a soma dos elementos de um vetor usando os algoritmos abaixo:

Soma(v, a, b)
    se a > b, devolva 0
    senao
      devolva v[a] + Soma(v, a + 1, b)

Soma_2(v,a,b)
    se a > b, devolva 0
    m = piso((a+b)/2)
    devolva Soma_2(v, m, b) + Soma_2(v, m + 1, b)

(sqrtrec)O cálculo da raiz quadrada $A$ de um número $N$, com um erro admissível $e$ pode ser feito da seguinte forma: $$raiz(N,A,e) = A ~~se~~ \vert A^2 - N\vert < e$$ $$raiz(N,A,e) = raiz(N, (A^2 + N)/2A, e)~~caso~~contrario$$ Defina a função recursiva para o cálculo da raiz quadrada conforme acima e um programa de teste conveniente. Caso a opção -l seja fornecida na linha de comando, liste a aproximação inicial dada para a raiz e todas as intermediárias até a apresentação do resultado final.

(palindromo)Usando uma função recursiva, faça um programa que verifique se um conjunto de palavras fornecidas interativamente pelo usuário é palíndroma, isto é, se escrita de trás para frente nos leva à mesma palavra. O programa primeiro deve obter todas as palavras. O fornecimento de palavras termina com a palavra FIM. Após esta fase, o programa deve mostrar na tela a lista de palavras que são palíndromas.

(somaelem)Utilizando uma função recursiva, faça um programa que calcule a soma dos elementos de uma matriz de números reais. A ordem da matriz é obtida a partir de dois argumentos que são fornecidos ao programa pela linha de comando.

(pintafig)Implemente um programa que faça o preenchimento de áreas em desenhos. Este programa deve receber 2 argumentos ao ser chamado: o nome de um arquivo e uma coordenada $x,y$. O arquivo é do tipo ASCII (texto) e contém uma matriz representando a imagem. A coordenada representa um ponto na imagem. O ponto $0,0$ corresponde ao canto inferior esquerdo da imagem. Dada a coordenada $x,y$ nesta matriz, realizar o preenchimento limitado às bordas estabelecidas no desenho. A imagem após o preenchimento deve ser gravada em um arquivo texto antes do término do programa. A figura 1 mostra um exemplo de imagem, considerando que foi fornecido $x,y$ = 5,4, e onde '*' $=$  côr de preenchimento, '.' $=$  côr de fundo a ser preenchido, '$' $=$  outra côr qualquer.

Figura 1: Exemplo de imagem (8x8 caracteres)