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)