Lista de Exercícios sobre Funções Recursivas (Programação)

Prévia do material em texto

Alcides Tiago Medeiros Dantas - 20211014040078 
TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS – IFRN 
Natal – RN 
2021 
LISTA DE EXERCÍCIOS – FUNÇÕES 
PROGRAMAÇÃO DE COMPUTADORES 
 
 
1. (10 pontos) Explique o que é uma função em um programa de computador. Mostre, 
com exemplos em Python, como definir uma função e o que acontece quando um 
programa chama uma função. 
 Uma função é um bloco de código com um nome associado que 
realiza alguma tarefa específica e pode ser executado a partir de qualquer parte 
do programa quantas vezes desejarmos. 
 
 Como definir uma função em Python: 
 def nome_da_função (parâmetros): 
 
 
 
 
 Segue abaixo um exemplo prático para mostrar como definir uma função em 
Python: 
 
def dobro_numero (n1, n2): 
 return n1*2, n2*2 
 
n1, n2 = map(int, input().split()) 
dobro = dobro_numero(n1,n2) 
print(dobro) 
 
 O programa acima lê dois números inteiros da entrada e em seguida declara 
uma variável chamada dobro, esta que chama a função dobro_numero passando como 
parâmetros exatamente os dois números lidos. Com isso, o fluxo do programa é 
direcionado para o funcionamento da função, ou seja, a variável dobro ficará 
aguardando o retorno da função para prosseguir com o restante do código. A função 
dobro_numero, por sua vez, recebe os dois números como parâmetros, e logo em 
seguida retorna o dobro de cada um dos valores. Após isso, o fluxo do programa 
retorna para a variável dobro, que foi quem chamou a função. Dessa forma, a variável 
dobro agora possui valores armazenados nela e o programa continua normalmente, 
exibindo ao final o dobro de cada um dos valores lidos anteriormente. 
 
Segue abaixo o fluxo simplificado do programa recém-explicado: 
 
 
 
 
 
 
 
 
 
Definir uma nova função 
Nome da função sem espaços 
em branco entre as palavras. 
Deve-se pôr dois pontos antes de 
introduzir o conteúdo da função. 
Deve-se informar dentro dos parênteses os 
parâmetros da função separados por vírgulas. 
 n1, n2 = map(int, input().split()) 
 
 dobro = dobro_numero(n1,n2) 
 
 
 
 print(dobro) 
 def dobro_numero (n1, n2): 
 return n1*2, n2*2 
2. (10 pontos) Explique, com exemplos em Python, o que é uma função recursiva. 
 Uma função recursiva é uma função que é definida em termos de si 
mesma, referindo-se a si própria. 
 A fim de explicar melhor como funciona uma função recursiva, segue 
abaixo um código em Python que calcula o fatorial de um número: 
 
 
 
 
 
 
 
 
 
 
 
 Na linha 6, um número inteiro é lido da entrada. Já na linha 7, dentro 
do print, a função calc_fatorial é acionada passando o número lido como 
parâmetro. A partir disso, o fluxo do programa é direcionado para a linha 1, 
que é a execução da função que foi invocada. Observando a linha 2, a priori o 
resultado do fatorial é inicialmente igual a 1, visto que o fatorial só será 
diferente disso quando o usuário digitar um número maior do que zero. Caso o 
usuário de fato digite um número maior do que zero (verificação feita na linha 
3), será realizado o cálculo do fatorial desse número na linha 4. Porém, para 
calcular o fatorial de um número, é necessário obter o fatorial do número 
anterior a ele para só depois chegar ao resultado, que é justamente a aplicação 
do conceito de função recursiva, que nesse caso, para definir o fatorial de um 
número através de uma função, é preciso usar a própria função para calcular o 
fatorial dos números anteriores e só então chegar no resultado. 
 Observe na imagem do lado esquerdo abaixo um exemplo referente às 
chamadas do cálculo do fatorial de 3 usando função recursiva: 
 
 
 
 
 
 
1. def calc_fatorial(n): 
2. resultado = 1 
3. if (n > 0): 
4. resultado = n * calc_fatorial(n - 1) 
5. return resultado 
 
6. num = int(input()) 
7. print("O fatorial de", num, "é", calc_fatorial(num)) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
3. (10 pontos) Escreva, em Python, uma função recursiva que determine se um número é 
primo. Escreva um texto explicando como você escreveu essa função. 
1. #Início da Função Recursiva 
2. def qtd_divisores_rec(num, divisor): 
3. if (divisor == 1): 
4. return 1 
5. quantidade_divisores = qtd_divisores_rec(num, divisor - 1) 
6. if (num % divisor == 0): 
7. quantidade_divisores += 1 
8. return quantidade_divisores 
9. #Fim da Função Recursiva 
 
10. #Início do Programa Principal 
11. num = int(input()) 
12. quantidade_divisores = qtd_divisores_rec(num, num) 
13. #Fim do trecho principal 
 
14. #Saída do Programa 
15. if (quantidade_divisores == 2): 
16. print("O número", num, "é primo!") 
17. else: 
18. print("O número", num, "NÃO é primo!") 
 
R: A função qtd_divisores definida na linha 2 desse programa, possui o objetivo de 
contar a quantidade de divisores de um número que foi digitado pelo usuário. A 
 Note que para calcular o fatorial de um número X qualquer, é 
preciso executar a própria função recursiva para calcular o fatorial 
do(s) número(s) anterior(es). 
X-1...X-2...X-3. 
 Ao chegar no fatorial de zero, temos que o resultado é igual a 1, 
então o programa volta para o cálculo do fatorial de 1, que foi 
quem chamou o fatorial de zero. 
Agora, o cálculo do fatorial de 1 já pode ser feito e é isso que 
ocorre, então o programa volta para o fatorial de 2 que foi quem 
chamou o fatorial de 1. 
 O fatorial de 2, por sua vez, já pode ser calculado, então o 
programa obtém seu resultado e retorna para o fatorial de 3, que 
finalmente é calculado, fazendo com que a função retorne para a 
linha do programa principal que chamou a função. 
partir dessa quantidade é possível saber se o número é primo ou não. Afinal, para 
um número ser primo, a quantidade de divisores dele precisa ser igual a 2 
(comparação feita na linha 15), que trata-se do número 1 e dele mesmo. 
 Abordando melhor o código para em seguida explicar a função recursiva, temos 
que na linha 12 é chamada a função qtd_divisores_rec passando como parâmetros o 
número digitado duas vezes, visto que a verificação para achar a quantidade de 
divisores daquele valor começa por ele mesmo ocupando o lugar do divisor, já que 
todo número é divisível por ele mesmo. Após a chamada da função, já adentrando 
no código dela, é feita uma verificação de parada na linha 3 a fim de saber se o 
divisor atual é igual a 1: 
 Caso essa condição seja verdadeira (divisor igual a 1), significa que o programa 
já verificou quais números anteriores ao valor digitado são divisores dele (linha 6) e 
adicionou-os a variável quantidade_divisores (linha 7), e atualmente se encontra na 
verificação do divisor igual a 1, retornando 1 ao final. 
 Caso contrário (divisor inicialmente não é igual a 1), o programa prossegue para 
a linha 5, local em que a variável quantidade_divisores é inicializada recebendo 
como valor a chamada recursiva da função qtd_divisores_rec passando como 
parâmetros tanto o número digitado pelo usuário quanto o valor da variável divisor 
subtraído de 1, visto que devem ser verificados todos os números abaixo do valor 
digitado, até que se chegue no divisor igual a 1, ocorrendo o que foi mencionado no 
parágrafo anterior. 
 
4. (10 pontos) Escreva, em python, e explique como funciona, uma função recursiva que 
determine a soma dos números pares de uma lista. 
1. def pares_rec(lista, tamanho_lista): 
2. if (tamanho_lista == 0): 
3. return [] 
 
4. ultimo_elemento = lista[tamanho_lista - 1] 
5. lista_pares = pares_rec(lista, tamanho_lista - 1) 
6. if (ultimo_elemento % 2 == 0): 
7. lista_pares.append(ultimo_elemento) 
8. return lista_pares 
 
9. lista = list(map(int, input().split())) 
10. tamanho_lista = len(lista) 
11. lista_pares = pares_rec(lista, tamanho_lista) 
12. print("") 
13. print("A lista de númerospares é:", lista_pares) 
14. print("A soma entre os números pares da lista é igual a:", sum(lista_pares)) 
 
R: A função pares_rec é definida na linha 1 e possui dois parâmetros: o primeiro é a 
lista que o usuário digitou, e o segundo é o tamanho dela, que vai ser útil para irmos 
diminuindo a lista original da direta para a esquerda e verificando se o último 
elemento é par ou não. Já na linha 2, é realizada uma verificação a fim de saber se a 
lista digitada pelo usuário contém algum elemento, caso não haja, a função retorna 
uma lista vazia (linha 3). Essa condição também é o ponto de paralização do 
programa, visto que quando não houver mais nenhum item na lista digitada pelo 
usuário a ser analisado, a verificação acaba. Na linha 4 é inicializada uma variável 
que vai receber sempre o último elemento da lista, que é justamente o valor que vai 
ser sempre checado na linha 6 a fim de saber se ele é par ou não, caso seja, esse 
elemento é adicionado ao final da lista dentro da variável lista_pares, que é quem 
vai armazenar todos os números pares coletados a partir da lista digitada. Voltando 
um pouco para a linha 5, temos justamente a chamada recursiva da função 
pares_rec, onde são passados como parâmetros a lista digitada e o tamanho dela 
sempre reduzido a 1, com o objetivo de ir diminuindo ela para poder saber se o 
último elemento a direita é par ou não. Esse processo se repete até que a lista 
analisada não possua mais nenhum elemento. 
 
5. (10 pontos) Sobre a função a seguir: 
def f(n,d): 
if (n==0): 
return 0 
res = 0 
if (n%10==d): 
res = res+1 
return res + f(n//10,d) 
 
Escreva a árvore de chamada para os valores 326172837831 e 3 (f(326172837821,3)). 
De- termine e explique o que faz a função. 
 
f(326172837831,3) 
o valor de “n” inicialmente não é igual a zero (condição de parada), então: 
 
 
 
 
 
 
 
res + f(326172837831//10, 3) 
res + f(32617283783//10, 3) 
n % 10 == 3? SIM! 
res = 0 + 1 
res = 1 
return 
3 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Explicação: A função recursiva acima divide de forma inteira o valor de “n” 
por 10 (movendo a vírgula para a esquerda) sucessivas vezes até que ele se 
encontre em zero, causando o retorno final da função pelo caso de base. 
res + f(3261728378//10, 3) 
res + f(326172837//10, 3) 
res + f(32617283//10, 3) 
n % 10 == 3? SIM! 
res = 1 + 1 
res = 2 
res + f(3261728//10, 3) 
res + f(326172//10, 3) 
res + f(32617//10, 3) 
res + f(3261//10, 3) 
res + f(326//10, 3) 
res + f(32//10, 3) 
res + f(3//10, 3) 
n % 10 == 3? SIM! 
res = 2 + 1 
res = 3 
res + f(0//10, 3) 
n == 0, condição de 
parada atingida! 
return 0 
return 
3 + 0 
return 
3 + 0 
return 
3 + 0 
return 
3 + 0 
return 
3 + 0 
return 
3 + 0 
return 
3 + 0 
return 
3 + 0 
return 
3 + 0 
return 
3 + 0 
Porém, enquanto o “n” não for zero, ocorrem as divisões sucessivas 
mencionadas anteriormente, a fim de verificar quando elas geram o resto 
igual a “d”, que possui o valor 3. Essa condição será verdadeira quando o 
número 3 se encontrar na última posição a direita do valor “n”, visto que 
após a realização da divisão de “n” por 10, a vírgula se deslocará para a 
esquerda e será justamente o número 3 que estará após ela (o mesmo que 
dizer: o resto da divisão de “n” por 10 é igual a 3), fazendo com que o 
programa contabilize +1 valor na variável “res” a cada vez que isso ocorrer. 
Ao final, quando o dividendo chegar a zero, a função irá retornar a 
quantidade de vezes em que a divisão de “n” por 10 resultou em resto 3. 
Nesse caso, o retorno final é igual a 3. 
 
6. (10 pontos) Escreva, em python, e explique como funciona, uma função recursiva 
que determine quantos bits são necessários para representar um determinado número, 
ignorando os zeros a esquerda. 
Exemplo: Para o número 1234 são necessários 11 bits, pois 1234(10) = 10011010010(2) 
 
1. def qtd_bits(n): 
2. if (n == 0): 
3. return 0 
4. 
5. bits = qtd_bits(n//2) 
6. bits += 1 
7. return bits 
8. 
9. numero = int(input()) 
10.print("O número {:d} precisa de {:d} bit(s) para ser representado em 
binário.".format(numero, qtd_bits(numero))) 
 
R: A função recursiva é definida na linha 1, com sua condição de parada 
presente na linha 2, que é quando o dividendo se encontra igual a zero e o 
cálculo da quantidade de bits que representa aquele número deve ser 
encerrado. Já na linha 5, ocorre o cálculo das divisões sucessivas do número 
digitado por dois, além da chamada recursiva passando como parâmetro o 
resultado inteiro dessa divisão, a fim de informar o próximo valor do 
dividendo que também será dividido por dois, até se chegar no dividendo igual 
a zero (linha 2), como dito anteriormente. Observando a linha 6, podemos 
notar a contagem de 1 em 1 da quantidade de bits que será necessária para 
representar tal número digitado, logo após a divisão ocorrida na linha 5. 
Quando o dividendo se encontrar em zero, o retorno da função finalmente é 
feito. 
 
7. (10 pontos) Escreva uma função recursiva que determine se os elementos de uma lista 
estão ordenados. A função deve retornar um valor lógico (boolean). 
 
 1. def Ordenados(lista, tamanho_lista): 
2. if (tamanho_lista == 0 or tamanho_lista == 1): 
3. return True 
4. 
5. ultimo = lista[tamanho_lista - 1] 
6. penultimo = lista[tamanho_lista - 2] 
7. 
8. if (ultimo >= penultimo): 
9. return Ordenados(lista, tamanho_lista - 1) 
10. 
11. else: 
12. return False 
13. 
14. lista = list(map(int, input().split())) 
15. print(Ordenados(lista, len(lista))) 
 
8. (10 pontos) Sobre a função recursiva a seguir: 
def f(x,y): 
if (x>=y): 
return (x+y)/2 
else: 
return f(f(x+2,y−1),f(x+1,y−2)) 
 
a. Desenhe a árvore de chamada para uma chamada f (1, 8). 
 
R: f(1, 8) –> x inicia menor do que zero, então o programa entra no seguinte return 
inicialmente: 
f(f(x+2,y−1) , f(x+1,y−2)) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
f(1+2,8−1) 
f(2,6) 
f(5,6) f(3,4) 
f(7,5) f(4,2) 
return (7+5)/2 
return 6 
return (4+2)/2 
return 3 
f(1+1,8−2) 
f(3,7) 
x se encontra maior do que y x se encontra maior do que y 
b. Mostre o resultado da chamada f (1, 8) obtido a partir da construção da 
árvore de chamada. 
 
f(f(x+2,y−1) , f(x+1,y−2)) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
c. Determine o que faz a função. 
 
R: De forma resumida, a função acima recebe dois parâmetros (x e y) e no fim das 
contas realiza a média entre eles dois, só que de forma recursiva e mais extensa. 
Adentrando no código, temos que quando o “x” se encontra maior do que o “y”, ocorre 
o cálculo da média entre os dois. Caso contrário, são feitas duas chamadas recursivas 
dentro de uma chamada recursiva maior, esta última que só é calculada quando as duas 
funções menores já realizaram seu retorno final contendo um valor obtido por elas. A 
partir daí, a função maior que já recebeu os valores das funções menores, possui um 
valor “x” no primeiro parâmetro e um valor “y” no segundo parâmetro, sendo que agora 
obrigatoriamente “x” já é maior do que “y” e pode-se observar que a soma entre eles é 
igual a soma dos valores de “x” e “y” que iniciaram o problema, logo, a média entre os 
dois valores que a função maior obtém como resultado é equivalente ao que seria a 
média entre os dois valores de “x” e “y” que iniciaram o problema.
f(1+1,8−2) 
2 
f(1+2,8−1) 
f(3,7) f(2,6) 
f(5,6) f(3,4) 
f(7,5) f(4,2) 
return (7+5)/2 
return 6 
return (4+2)/2 
return 3 
6 
6 
6 
6 
6 
3 
3 
3 
3 
• f(6 , 3) 
• (6+3)/2 
4.5 --> Resultado 
k 
n Se k = 1 
 1 Se n = k 
k−1 k 
 
9. (10 pontos) Uma combinação sem repetição, em análise combinatória, é um 
subconjunto com k elementos em umconjunto U, com n elementos1. A quantidade 
de subconjuntos distintos pode ser calculado pela fórmula: 
Cn = 
n! 
k! × (n − k)! 
Esta função pode ser definida recursivamente como: 
 
 
 cn−1 + Cn−1 Se 1 ≤ k ≤ n 
Escreva uma função recursiva em Python, def comb(n,k):, que calcule o valor de Cn, 
Desenhe a árvore de recursão para a chamada comb(6,4) e comb(6,3). 
 
def calculo_combinacao(n, k): 
 if (n == k): 
 return 1 
 elif (k == 1): 
 return n 
 
 resultado = calculo_combinacao(n-1, k-1) + calculo_combinacao (n-1, k) 
 return int(resultado) 
 
n = int(input()) 
k = int(input()) 
 
print(calculo_combinacao(n, k)) 
 
• Árvore de chamada de calculo_combinacao(6,4): 
Com o valor 6 para “n” e o valor 4 para “k”, o programa ainda não se direciona para 
nenhuma das condições de parada, sendo assim: 
 
calculo_combinacao(n-1, k-1) + calculo_combinacao (n-1, k) 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
calculo_combinacao(6, 4) calculo_combinacao(6, 4) 
calculo_combinacao(5, 3) calculo_combinacao(5, 4) 
calculo_combinacao(4, 2) calculo_combinacao(4, 4) 
calculo_combinacao(3, 1) 
return 1 
return 3 
k C
n = 
k 
• Árvore de chamada de calculo_combinacao(6,3): 
Com o valor 6 para “n” e o valor 3 para “k”, o programa ainda não se direciona para 
nenhuma das condições de parada, sendo assim: 
 
calculo_combinacao(n-1, k-1) + calculo_combinacao (n-1, k) 
 
 
 
 
 
 
 
 
 
 
 
10. (10 pontos) Seja o polinômio 
Pn(x) = a0xn + a1xn−1 + a2xn−2 + . . . + an−1x + an 
Que pode ser calculado através da definição recursiva a seguir: 
Pn(x) = x.Pn−1(x) + an 
onde 
Pn−1(x) = a0xn−1 + a1xn−2 + . . . + an−2x + an−1 
Escreva uma função recursiva Pn(x). A função deve receber como parâmetro uma lista 
(array) com os coeficientes do polinômio e o valor de x. 
def polinomio(coeficientes,x): 
 
 
Exemplo O polinômio: 
 
 
P4(x) = 2x4 + 6x3 + 3x2 + 4x1 + 5 
 
pode ser calculado como: P4(x) = x × P3(x) + 5 
onde P3(x) = x × P2(x) + 4 
Exemplo de chamada da função 
coef = [2,6,3,4,5] 
x = 10 
resultado = polinomio(coef,x) 
print(resultado) 
 
 
 
 
1https://pt.wikipedia.org/wiki/Combinação 
 
 
 
 
 
calculo_combinacao(6, 3) calculo_combinacao(6, 3) 
calculo_combinacao(5, 2) calculo_combinacao(4, 3) 
calculo_combinacao(4, 1) calculo_combinacao(3, 3) 
return 4 return 1 
https://pt.wikipedia.org/wiki/Combinação
Resposta: 
 
1. def polinomio(lista, x, tamanho_lista): 
2. if (tamanho_lista == 0): 
3. return 0 
4. 
5. ultimo = lista[tamanho_lista - 1] 
6. polinomios = polinomio(lista, x, tamanho_lista - 1) 
7. 
8. return x * polinomios + ultimo 
9. 
10. lista_coeficientes = list(map(int, input().split())) 
11. x = 10 
12. print(polinomio(lista_coeficientes, x, len(lista_coeficientes)))