Recursão
Exercícios copiados da página Projeto de Algoritmos em C de Paulo Feofiloff.
Exercício 1
A função abaixo promete encontrar o valor de um elemento máximo de v[0:n]
. A função cumpre a promessa?
def (v):
n = len(v)
m = v[0]
for j in range( n ):
if v[j-1] < v[j]: m = v[j]
return m
Exercício 2
Critique a seguinte função recursiva; ela promete encontrar o valor de um elemento máximo de v[0..n-1].
def maximoR1 (n, v):
if n == 1: return v[0]
if n == 2:
if v[0] < v[1]: return v[1]
else: return v[0]
x = maximoR1(n, v)
if x < v[n-1]: return v[n-1]
return x
Exercício 3
Critique a seguinte função recursiva, que promete encontrar o valor de um elemento máximo de v[0..n-1].
def maximoR2 (n, v):
if n == 1: return v[0]
if maximoR2(n-1, v) < v[n-1]:
return v[n-1]
return maximoR2(n-1, v)
Exercício 4
Escreva uma função recursiva que calcule o produto dos elementos estritamente positivos de uma lista de inteiros v[0:n]
. O problema faz sentido quando todos os elementos do vetor são nulos? O problema faz sentido quando n
vale 0? Quanto deve valer o produto nesses casos?
Exercício 5
A função maximo()
discutida em aula aplica a recursão ao segmento v[0:n-1]
da lista. É possível escrever uma versão que aplique a recursão ao segmento v[1:n]
:
def maximo2(v):
'''(list) -> valor
Recebe uma lista v e um inteiro n >= 1, e retorna
o valor de um elemento máximo da lista v
'''
return maxR(0, len(v), v)
A função maximo2()
é apenas uma "embalagem" ou "invólucro" (= wrapper-function); o serviço pesado é executado pela função recursiva maxR()
.
A função maxR()
resolve um problema mais geral que o original. Qual? A necessidade de generalizar o problema original ocorre com frequência no projeto de algoritmos recursivos.
Escreva a função maxR()
.
Exercício 6
A seguinte função recursiva promete encontrar o valor de um elemento máximo de v[p:u]
, supondo p <= u
. O índice p
indica o primeiro elemento da lista e o índice u
indica o último. A função está correta? Suponha que p
e u
valem 0 e 6 respectivamente e mostre a sequência, devidamente indentada, de chamadas de max()
.
def max(p, u, v):
if p == u: return v[u]
else:
m = (p + u)///2 # p <= m < u
x = max(p, m, v)
y = max(m+1, u, v)
if x >= y: return x
return y
Exercício 7
Escreva uma função recursiva que calcule a soma dos elementos positivos da lista v[p:u]
. O problema faz sentido quando p
é igual a u
? Quanto deve valer a soma nesse caso?
Exercício 8
Diga o que a função abaixo faz. Para quais valores dos parâmetros sua resposta está correta?
def ttt (x, n):
if n == 0: return 0
if x[n] > 100: return x[n] + ttt(x, n-1)
return ttt(x, n-1)
Exercício 9
Escreva uma função recursiva que calcule a soma dos dígitos de um inteiro estritamente positivo n
. A soma dos dígitos de 132, por exemplo, é 6.
Exercício 10
Qual o valor de X(4)
?
def X( n ):
if n == 1 or n == 2: return n
return X(n-1) + n*X(n-2)
Exercício 11
Qual é o valor de f(1,10)
? Escreva uma função equivalente que seja mais simples.
def f(x, y):
if x >= y: return (x + y)/2
return f(f(x+2, y-1), f(x+1, y-2))
}
Exercício 12
Qual o resultado da execução do seguinte programa?
def main():
print("%d"%(ff(7)))
def ff( n ):
if n == 1: return 1
if n % 2 == 0: return ff(n/2)
return ff((n-1)/2) + ff((n+1)/2)
main()
Exercício 13
Execute fusc(7,0)
. Mostre a sequência, devidamente indentada, das chamadas a fusc()
.
def fusc(n, profund):
for i in range(profund):
print(" ", end="")
print ("fusc(%d,%d)"%(n, profund))
if n = 1: return 1
if n % 2 == 0: return fusc(n/2, profund+1)
return fusc((n-1)/2, profund+1) + fusc((n+1)/2, profund+1)
Exercício 14
Critique a seguinte função recursiva:
def XX( n ):
if n == 0: return 0
return XX(n/3+1) + n
Exercício 15
Fibonacci. A função de Fibonacci é definida assim:
F(0) = 0, F(1) = 1 e F( n ) = F(n-1) + F(n-2) para n > 1.
Descreva a função F()
. Faça uma versão iterativa e uma recursiva. Seja F()
a versão recursiva da função de Fibonacci. O cálculo do valor da expressão F(3)
provocará a seguinte sequência de invocações da função:
F(3)
F(2)
F(1)
F(0)
F(1)
Qual a sequência de invocações da função durante o cálculo de F(5)
?
Exercício 16
Euclides. A seguinte função calcula o maior divisor comum dos inteiros estritamente positivos m
e n
. Escreva uma função recursiva equivalente.
def Euclides(m, n):
r = m % n;
while r != 0:
m = n
n = r
r = m % n
return n
Exercício 17
Exponenciação. Escreva uma função recursiva eficiente que receba inteiros estritamente positivos k
e n
e calcule k^n
. Quantas multiplicações sua função executa aproximadamente?
Exercício 18
Régua inglesa: Escreva uma função recursiva que imprima uma régua de ordem n
em [0:2n+1]
. O "traço" no ponto médio da régua deve ter comprimento n, os traços nos pontos médios dos subintervalos superior e inferior devem ter comprimento n-1
, e assim por diante. A figura mostra uma régua de ordem 4.
.
. -
. --
. -
. ---
. -
. --
. -
. ----
. -
. --
. -
. ---
. -
. --
. -
.
(Editado por Lucas Santos - sábado, 18 Nov 2017, 13:22)