Recursão em Programação Orientada a Objetos

Prévia do material em texto

Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 1/45
Recursão – Lista de exercícios
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 2/45
Solução lista de exercícios
● Vamos tentar, antes de mais nada, estabelecer 
como seria a definição recursiva do problema
● Depois usaremos na implementação
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 3/45
Exercício 3
● 3) Implemente uma função recursiva que, 
dados dois números inteiros x e n, calcula o 
valor de xn.
● Caso base? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 4/45
Exercício 3
● 3) Implemente uma função recursiva que, 
dados dois números inteiros x e n, calcula o 
valor de xn.
● Caso base? x0 = 1 
● Passo da recursão: 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 5/45
Exercício 3
● 3) Implemente uma função recursiva que, 
dados dois números inteiros x e n, calcula o 
valor de xn.
● Caso base? x0 = 1 
● Passo da recursão: xn = x * xn-1 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 6/45
Exercício 3
int pot(int b, int p)
{
   if ( p == 0 ) return 1;
   return ( b * pot(b, p­1));
} 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 7/45
Exercício 7
● 7) Usando recursividade, calcule a soma de 
todos os valores de um array de reais.
● Caso base? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 8/45
Exercício 7
● 7) Usando recursividade, calcule a soma de 
todos os valores de um array de reais.
● Caso base? Tamanho do array = 0. Soma é 0. 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 9/45
Exercício 7
● 7) Usando recursividade, calcule a soma de 
todos os valores de um array de reais.
● Caso base? Tamanho do array = 0. Soma é 0. 
● Passo da recursão:
v
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 10/45
Exercício 7
● 7) Usando recursividade, calcule a soma de todos os 
valores de um array de reais.
● Caso base? Tamanho do array = 0. Soma é 0. 
● Passo da recursão:
v
v[n-1] + soma do restante do array. 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 11/45
Exercício 7
int soma_a(int v[], int n)
{
   if ( n == 0 ) return 0;
   return v[n­1] + soma(v, n­1);
}
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 12/45
Exercício 1
● 1) Dado um array de inteiros e o seu número 
de elementos, inverta a posição dos seus 
elementos.
● Caso base? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 13/45
Exercício 1
● 1) Dado um array de inteiros e o seu número de 
elementos, inverta a posição dos seus elementos.
● Caso base? Tamanho do array menor ou igual a 1 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 14/45
Exercício 1
● 1) Dado um array de inteiros e o seu número de 
elementos, inverta a posição dos seus elementos.
● Caso base? Tamanho do array menor ou igual a 1 
● Passo da recursão: 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 15/45
Exercício 1
● 1) Dado um array de inteiros e o seu número de elementos, 
inverta a posição dos seus elementos.
● Caso base? Tamanho do array menor ou igual a 1 
● Passo da recursão: 
● Troca 1o. e último elementos e inverte resto do array.
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 16/45
Exercício 1
void inverte(int v[], int esq, int dir)
{
int t;
   if (esq >= dir) return;
   t = v[esq];
   v[esq] = v[dir];
   v[dir] = t;
   inverte(v, esq+1, dir ­ 1);
}
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 17/45
Exercício 9
● 9) Escreva uma função recursiva que determine quantas 
vezes um dígito K ocorre em um número natural N. Por 
exemplo, o dígito 2 ocorre 3 vezes em 762021192.
● Caso base? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 18/45
Exercício 9
● 9) Escreva uma função recursiva que determine quantas 
vezes um dígito K ocorre em um número natural N. Por 
exemplo, o dígito 2 ocorre 3 vezes em 762021192.
● Caso base? Quando todos os digitos já foram 
examinados, ou seja, N = 0
 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 19/45
Exercício 9
● 9) Escreva uma função recursiva que determine quantas 
vezes um dígito K ocorre em um número natural N. Por 
exemplo, o dígito 2 ocorre 3 vezes em 762021192.
● Caso base? Quando todos os digitos já foram 
examinados, ou seja, N = 0
 
● Passo da recursão: n4n3n2n1n0
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 20/45
Exercício 9
● 9) Escreva uma função recursiva que determine quantas 
vezes um dígito K ocorre em um número natural N. Por 
exemplo, o dígito 2 ocorre 3 vezes em 762021192.
● Caso base? Quando todos os digitos já foram 
examinados, ou seja, N = 0
 
● Passo da recursão: n4n3n2n1n0
(0 ou 1) + número de ocorrências em N / 10 (n4n3n2n1)
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 21/45
Exercício 9
int conta_dig(int N, int K)
{
   if ( N == 0 ) return 0;
   return conta_dig( N / 10 , K) + ( N % 10 == K );
}
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 22/45
Exercício 4
● 4) Um problema típico em ciência da computação consiste 
em converter um número da sua forma decimal para a 
forma binária. 
● Caso base? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 23/45
Exercício 4
● 4) Um problema típico em ciência da computação consiste 
em converter um número da sua forma decimal para a 
forma binária. 
● Caso base? Quando o número já foi todo transformado 
em binário. Ou seja: x = 0
● Passo da recursão: 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 24/45
Exercício 4
● 4) Um problema típico em ciência da computação consiste 
em converter um número da sua forma decimal para a 
forma binária. 
● Caso base? Quando o número já foi todo transformado 
em binário. Ou seja: x = 0
● Passo da recursão: Saber como x/2 é convertido. Depois, 
adicionar um dígito (o ou 1) relativo a x.
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 25/45
Exercício 4
void print_bin(int x)
{
   if ( x == 0 ) return;
   print_bin(x / 2);
   printf("%d", x % 2);
}
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 26/45
Exercício 4
void print_bin(int x)
{
   if ( x == 0 ) return;
   print_bin(x / 2);
   printf("%d", x % 2);
}
void print_bin(int x)
{
   if ( x == 0 ) 
   {
     printf("0");
     return;
   }
   print_bin(x / 2);
   printf("%d", x % 2);
}
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 27/45
Exercício 5
● 5) O máximo divisor comum (MDC) de dois 
números inteiros x e y pode ser calculado 
usando-se uma definição recursiva:
● MDC(x, y) = MDC(x − y, y), se x > y
● MDC(x,y) = MDC(y,x)
● MDC(x,x) = x
● Caso base? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 28/45
Exercício 5
● 5) O máximo divisor comum (MDC) de dois 
números inteiros x e y pode ser calculado 
usando-se uma definição recursiva:
● MDC(x, y) = MDC(x − y, y), se x > y
● MDC(x,y) = MDC(y,x)
● MDC(x,x) = x
● Caso base? x == y
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 29/45
Exercício 5
● 5) O máximo divisor comum (MDC) de dois 
números inteiros x e y pode ser calculado usando-
se uma definição recursiva:
● MDC(x, y) = MDC(x − y, y), se x > y
● MDC(x,y) = MDC(y,x)
● MDC(x,x) = x
● Caso base? x == y
● Passo da recursão? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 30/45
Exercício 5
● 5) O máximo divisor comum (MDC) de dois números 
inteiros x e y pode ser calculado usando-se uma 
definição recursiva:
● MDC(x, y) = MDC(x − y, y), se x > y
● MDC(x,y) = MDC(y,x)
● MDC(x,x) = x
● Caso base? x == y
● Passo da recursão? Os dois outros casos acima. O 
problema é definido recursivamente. 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP31/45
Exercício 5
int mdc(int p, int q)
{
   if ( p == q ) return p;
   if ( p < q ) return mdc(q, p);
   return mdc(p ­ q, q);
}
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 32/45
Exercício 6
● 6) Pode-se calcular o resto da divisão, MOD, de x por y, dois 
números inteiros positivos, usando-se a seguinte definição:
● MOD(x,y) = MOD(x - y, y) se x > y
● MOD(x,y) = x se x < y
● MOD(x,y) = 0 se x = y
● Caso base? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 33/45
Exercício 6
● 6) Pode-se calcular o resto da divisão, MOD, de x por y, dois 
números inteiros positivos, usando-se a seguinte definição:
● MOD(x,y) = MOD(x - y, y) se x > y
● MOD(x,y) = x se x < y
● MOD(x,y) = 0 se x = y
● Caso base? São dois: x < y ou x = y 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 34/45
Exercício 6
● 6) Pode-se calcular o resto da divisão, MOD, de x por y, dois 
números inteiros positivos, usando-se a seguinte definição:
● MOD(x,y) = MOD(x - y, y) se x > y
● MOD(x,y) = x se x < y
● MOD(x,y) = 0 se x = y
● Caso base? São dois: x < y ou x = y 
● Passo da recursão: 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 35/45
Exercício 6
● 6) Pode-se calcular o resto da divisão, MOD, de x por y, dois 
números inteiros positivos, usando-se a seguinte definição:
● MOD(x,y) = MOD(x - y, y) se x > y
● MOD(x,y) = x se x < y
● MOD(x,y) = 0 se x = y
● Caso base? São dois: x < y ou x = y 
● Passo da recursão: MOD(x - y, y) se x > y
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 36/45
Exercício 2a
● 2) Escreva as funções recursivas que unem dois (arrays), 
sem elementos repetidos, classificadas considerando que 
as duas listas não têm elementos em comum
● Caso base? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 37/45
Exercício 2a
● 2) Escreva as funções recursivas que unem dois (arrays), 
sem elementos repetidos, classificadas considerando que 
as duas listas não têm elementos em comum
● Caso base? Quando ambos os arrays têm tamanho 0
 
● Passo da indução: 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 38/45
Exercício 2a
● 2) Escreva as funções recursivas que unem dois (arrays), 
sem elementos repetidos, classificadas considerando que 
as duas listas não têm elementos em comum
● Caso base? Quando ambos os arrays têm tamanho 0
 
● Passo da indução: 
Menor deles
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 39/45
Exercício 2a
● 2) Escreva as funções recursivas que unem dois (arrays), 
sem elementos repetidos, classificadas considerando que 
as duas listas não têm elementos em comum
● Caso base? Quando ambos os arrays têm tamanho 0
 
● Passo da indução: 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 40/45
Exercício 2a
void merge(int v1[], int n1, 
           int v2[], int n2, int v3[]) 
{
    if ( n1 == 0 && n2 == 0 ) return;
    if (n1 == 0) {
      v3[0] = v2[0];
      merge(v1, n1, ++v2, ­­n2, ++v3);
    }
    else
    if (n2 == 0) {
      v3[0] = v1[0];
      merge(++v1, ­­n1, v2, n2, ++v3);
    }
    else
    if (v1[0] <= v2[0]) {
      v3[0] = v1[0];
      merge(++v1, ­­n1, v2, n2, ++v3);
    }
    else {
      v3[0] = v2[0];
      merge(v1, n1, ++v2, ­­n2, ++v3);
    }
 }
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 41/45
Exercício 2c
void merge(int v1[], int n1, 
           int v2[], int n2, int v3[]) 
{
    if ( n1 == 0 && n2 == 0 ) return;
    if (n1 == 0) {
      v3[0] = v2[0];
      merge(v1, n1, ++v2, ­­n2, ++v3);
    }
    else
    if (n2 == 0) {
      v3[0] = v1[0];
      merge(++v1, ­­n1, v2, n2, ++v3);
    }
    else
   if (v1[0] < v2[0]) {
      v3[0] = v1[0];
      merge(++v1, ­­n1, v2, n2, ++v3);
    }
    else
    if (v1[0] > v2[0]){
      v3[0] = v2[0];
      merge(v1, n1, ++v2, ­­n2, ++v3);
    }
    else {
      v3[0] = v2[0];
      merge(++v1,­­n1,++v2,­­n2, ++v3);
     }
 }
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 42/45
Exercício 8
● 8) Escreva um algoritmo recursivo capaz de 
gerar todos os elementos do conjunto potência 
dado um conjunto formado por letras.
● Caso base? 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 43/45
Exercício 8
● 8) Escreva um algoritmo recursivo capaz de 
gerar todos os elementos do conjunto potência 
dado um conjunto formado por letras.
● Caso base? 2{} = {}
● Passo da recursão: 
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 44/45
Exercício 8
● 8) Escreva um algoritmo recursivo capaz de 
gerar todos os elementos do conjunto potência 
dado um conjunto formado por letras.
● Caso base? 2{} = {}
● Passo da recursão: 
2{a,b,c} = 2{b,c} U {a} x 2{b,c}
Programação Orientada a Objetos – Prof Marcio Delamaro – ICMC/USP 45/45
Exercício 8
void potencia(char pref[], 
char s[], char *p) {
int l; char aux[100];
    l = strlen(s);
    if ( l == 0 )   {
       if (strlen(pref) == 
0 )
            strcpy(p, "{}");
        else {
            strcat(p, " ");
            strcat(p, pref);
        }
        return;
    }
    potencia(pref, s+1, p);
    strcpy(aux, pref);
    l = strlen(aux);
    aux[l] = s[0];
    aux[l+1] = '\0';
    potencia(aux, s+1, p);
    return;
}
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45