Recurcividade

SCC 201/501 — Introdução à Ciência de Computação II

(ICMC/USP)

Lista de Exercícios 2: Recursividade
Professor: Moacir Pereira Ponti Jr. PAE(s): Pâmela/Paulo Henrique

1. Mostre, através de teste de mesa, o resultado das seguintes funções: (i) int f1(int n)
{ if (n == 0) return (1); else return(n * f1(n-1)); }

Considere as entradas: i. f 1(0); ii. f 1(1); iii. f 1(5); (ii) int f2(int n)
{ if (n == 0) return (1); if (n == 1) return (1); else return(f2(n-1)+ 2 * f2(n-2)); }

Considere as entradas: i. f 2(0); ii. f 2(1); iii. f 2(5); (iii) int f3(int n)
{ if (n == 0) printf(“Zero ”); else { printf(“%d ”,n); printf(“%d ”,n); f3(n-1); } }

Considere as entradas: 1

i. f 3(0); ii. f 3(1); iii. f 3(5); 2. Desenvolva algoritmos recursivos para os seguintes problemas: (i) Impressão de um número natural em base binária. (ii) Multiplicação de dois números naturais, através de somas sucessivas (Ex.: 6 ∗ 4 = 4 + 4 + 4 + 4 + 4 + 4). (iii) Soma de dois números naturais, através de incrementos sucessivos (Ex.: 3 + 2 = + + (+ + 3)). (iv) Multiplicação de dois números naturais, através de incrementos sucessivos. (v) Cálculo de 1 + (vi) Cálculo de
2 4 1 2 5 5

+ +

1 3

+

1 4

+ ... +
17 7

1 N.

+

10 6

+

+

26 8

+ ... +

(n2 +1) (n+3) .

(vii) Inversão de uma string. (viii) Gerador da sequência dada por: • F (1) = 1 • F (2) = 2 • F (n) = 2 ∗ F (n − 1) + 3 ∗ F (n − 2). (ix) Gerador de Sequência de Ackerman: • A(m, n) = n + 1, se m = 0 • A(m, n) = A(m − 1, 1), se m = 0 e n = 0 • A(m, n) = A(m − 1, A(m, n − 1)), se m = 0 e n = 0. (x) A partir de um vetor de números inteiros, calcule a soma e o produto dos elementos do vetor. (xi) Gerador de máximo divisor comum (mdc): • mdc(x, y) = y, se x ≥ y e x mod y = 0 • mdc(x, y) = mdc(y, x), se x < y • mdc(x, y) = mdc(y, x mod y), caso contrário. (xii) Verifique se uma palavra é palíndromo (Ex. aba, abcba, xyzzyx). (xiii) Dado um número n, gere todas as possíveis combinações com as n