Exercício 01: Usando recursividade, calcule a soma de todos os valores de um vetor.
In [ ]:
Exercício 02: Usando recursividade, encontre o maior elemento de um vetor.
In [ ]:
Exercício 03: Faça uma função recursiva que inverta os elementos de um vetor.
In [ ]:
Exercício 04: Crie uma função recursiva que recebe os argumentos base e exp e calcule $base^{exp}$. Considere que exp é sempre inteiro. Não é permitido utilizar o operador ** ou laço de repetição em nenhum momento.
In [ ]:
Exercício 05: Crie uma função recursiva que verifica se um número n é primo.
In [ ]:
Exercício 06: Escreva um algoritmo recursivo capaz de gerar todas as permutações de uma string. Utilzie o código abaixo como referência.
In [1]:
def Permuta_NAO_RECURSIVO(s):
l, p = [([], list(s))], []
while len(l) > 0:
i, j = l.pop(0)
if len(j) > 0:
for c in range(len(j)):
l.append((i+[j[c]],j[:c]+j[c+1:]))
else:
p += ["".join(i)]
return p
print(Permuta_NAO_RECURSIVO("AB"))
print(Permuta_NAO_RECURSIVO("XYZ"))
print(Permuta_NAO_RECURSIVO("1234"))
Exercício 07: Uma imagem discreta pode ser representada através de uma matriz. Se considerar que o valor 0 de cada pixel representa espaço vazio, valor 2 representa um contorno e valor 1 representa preenchimento, implemente uma função recursiva que preencha o conteúdo interno de uma imagem delimitada pelo contorno (Boundary-fill). Utilize o código abaixo como referência. Note que é fornecido a posição inicial para realizar o preenchimento.
In [2]:
%pylab inline
import matplotlib.pyplot as plt
img = [[2,2,2,2,2,2,2,0,2,2,2,0],
[2,0,0,0,2,0,2,2,2,0,2,0],
[2,0,2,0,0,0,0,0,0,0,2,0],
[2,2,2,2,0,2,2,0,2,2,2,0],
[2,0,0,2,0,0,0,0,0,0,2,0],
[2,2,2,2,0,0,2,2,0,0,2,2],
[2,0,0,0,0,2,2,2,2,0,0,2],
[2,0,2,2,0,2,0,2,0,0,2,2],
[2,0,0,2,0,0,0,0,0,2,2,0],
[2,2,0,2,2,2,2,2,0,2,2,0],
[2,0,0,0,2,0,0,2,0,0,2,0],
[2,2,2,2,2,0,0,2,2,2,2,0]]
def Mostrar(img):
fig, ax = plt.subplots(1, 1, tight_layout=True)
my_cmap = matplotlib.colors.ListedColormap(['white', 'blue', 'black'])
my_cmap.set_bad(color='white', alpha=0)
for x in range(len(img)):
ax.axhline(x, lw=1, color='black', zorder=5)
ax.axvline(x, lw=1, color='black', zorder=5)
ax.imshow(img, interpolation='none', cmap=my_cmap, extent=[0, len(img), 0, len(img)], zorder=0)
ax.axis('off')
plt.show()
def Preencher_NAO_RECURSIVO(img, i, j):
def Verifica(u, v):
if u < 0 or u >= len(img) or j < 0 or j >= len(img[u]): # Se fora da imagem...
return False
elif img[u][v] == 1 or img[u][v] == 2: # Fim da imagem ou já preenchido...
return False
return True
l = [(i,j)] # Lista dos pixels que deversão ser preenchidos.
while(len(l) > 0): # Enquanto houver pixels para serem verificados/preenchidos, faça...
i, j = l.pop(0) # Remove e atribui o primeiro item da lista.
if Verifica(i,j):
img[i][j] = 1
# Coloca na fila os pixels vizinhos, se possível...
for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
if Verifica(i+di,j+dj):
l.append((i+di,j+dj))
Preencher_NAO_RECURSIVO(img, 3, 4) # Implemente a função de forma RECURSIVA
Mostrar(img)
In [5]:
%pylab inline
import matplotlib.pyplot as plt
img = [[2,2,2,2,2,2,2,0,2,2,2,0],
[2,0,0,0,2,0,2,2,2,0,2,0],
[2,0,2,0,0,0,0,0,0,0,2,0],
[2,2,2,2,0,2,2,0,2,2,2,0],
[2,0,0,2,0,0,0,0,0,0,2,0],
[2,2,2,2,0,0,2,2,0,0,2,2],
[2,0,0,0,0,2,2,2,2,0,0,2],
[2,0,2,2,0,2,0,2,0,0,2,2],
[2,0,0,2,0,0,0,0,0,2,2,0],
[2,2,0,2,2,2,2,2,0,2,2,0],
[2,0,0,0,2,0,0,2,0,0,2,0],
[2,2,2,2,2,0,0,2,2,2,2,0]]
def Mostrar(img):
fig = plt.figure()
my_cmap = matplotlib.colors.ListedColormap(['white', 'blue', 'black'])
my_cmap.set_bad(color='white', alpha=0)
plt.imshow(img, interpolation='none', cmap=my_cmap, extent=[0, len(img), 0, len(img)], zorder=0)
plt.grid(b=True, which='both', color='0.65',linestyle='-')
plt.xticks(range(len(img)), [])
plt.yticks(range(len(img)), [])
plt.show()
def Preencher_NAO_RECURSIVO(img, i, j):
def Verifica(u, v):
if u < 0 or u >= len(img) or j < 0 or j >= len(img[u]): # Se fora da imagem...
return False
elif img[u][v] == 1 or img[u][v] == 2: # Fim da imagem ou já preenchido...
return False
return True
l = [(i,j)] # Lista dos pixels que deversão ser preenchidos.
while(len(l) > 0): # Enquanto houver pixels para serem verificados/preenchidos, faça...
i, j = l.pop(0) # Remove e atribui o primeiro item da lista.
if Verifica(i,j):
img[i][j] = 1
# Coloca na fila os pixels vizinhos, se possível...
for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
if Verifica(i+di,j+dj):
l.append((i+di,j+dj))
Preencher_NAO_RECURSIVO(img, 3, 4) # Implemente a função de forma RECURSIVA
Mostrar(img)
In [ ]: