Lista de exercícios recursão em C

Prévia do material em texto

Algoritmos e Programac¸a˜o (Prof. Marcelo S. Zanetti - DELC - CT - UFSM ): Lista 3
Recursa˜o
(1) Explique com suas pro´prias palavras o que e´ recursa˜o;
(2) Escreva uma func¸a˜o que fac¸a a soma de dois inteiros a + b, de forma recur-
siva, retornando um inteiro como resultado. Utilize o seguinte proto´tipo: int
soma(int,int);
(3) Escreva uma func¸a˜o que fac¸a a subtrac¸a˜o de dois inteiros a − b, de forma
recursiva, retornando um inteiro como resultado. Utilize o seguinte proto´tipo:
int subtracao(int,int);
(4) Escreva uma func¸a˜o que fac¸a a multiplicac¸a˜o de dois inteiros a× b, de forma
recursiva, retornando um inteiro como resultado. Utilize o seguinte proto´tipo:
int multiplicacao(int,int);
(5) Escreva uma func¸a˜o que ca´lcule o piso da divisa˜o de dois inteiros ba
b
c, de forma
recursiva, retornando um inteiro como resultado. Utilize o seguinte proto´tipo:
int divisao(int,int);
(6) Escreva uma func¸a˜o recursiva que retorne um inteiro representando o resto
da divisa˜o de dois inteiros a
b
. Utilize o seguinte proto´tipo: int resto(int,int);
(7) Escreva uma func¸a˜o recursiva que retorne o ma´ximo divisor comum entre
dois inteiros. Utilize o seguinte proto´tipo: int mdc(int,int);
(8) Escreva uma func¸a˜o recursiva que retorne o ma´ximo elemento de um vetor.
A func¸a˜o deve receber um vetor de inteiros e um inteiro representando o indice
do u´ltimo elemento do respectivo vetor. Utilize o seguinte proto´tipo: int max(int
[],int);
(9) Escreva uma func¸a˜o recursiva que retorne o mı´nimo elemento de um vetor.
A func¸a˜o deve receber um vetor de inteiros e um inteiro representando o indice
do u´ltimo elemento do respectivo vetor. Utilize o seguinte proto´tipo: int min(int
[],int);
(10) Escreva uma func¸a˜o recursiva que retorne a me´dia de um vetor. A func¸a˜o
deve receber um vetor de nu´meros reais, um inteiro representando o indice do
u´ltimo elemento do respectivo vetor e um inteiro representando a quantidade de
elementos desse vetor. Utilize o seguinte proto´tipo: float media(float [],int,int);
Pa´gina 1 de 3
Algoritmos e Programac¸a˜o (Prof. Marcelo S. Zanetti - DELC - CT - UFSM ): Lista 3
(11) Escreva uma func¸a˜o recursiva que retorne o fatorial de um nu´mero inteiro.
Utilize o seguinte proto´tipo: int fatorial(int);
(12) Escreva uma func¸a˜o recursiva que receba um inteiro n e ca´lcule o seguinte
somato´rio
∑n
i=1 i. Utilize o seguinte proto´tipo: int somatorio(int);
(13) Escreva uma func¸a˜o recursiva que receba um inteiro n e ca´lcule o blog2 nc,
ou seja, o piso do logaritmo de n na base 2. Utilize o seguinte proto´tipo: int
log2(int);
(14) Escreva uma func¸a˜o recursiva que fac¸a a busca sequencial em um vetor.
A func¸a˜o deve receber um vetor inteiro, um inteiro representando o indice do
u´ltimo elemento desse vetor e um inteiro correpondente ao valor que deve ser
localizado no vetor. Se o elemento for encontrado a func¸a˜o retorna 1, sena˜o
retorna 0. Utilize o seguinte proto´tipo: int busca sequencial(int [], int, int);
(15) Escreva uma func¸a˜o recursiva que fac¸a a busca bina´ria em um vetor. A
func¸a˜o deve receber um vetor inteiro, um inteiro representando o indice do
primeiro elemento desse vetor, um inteiro representando o indice do u´ltimo ele-
mento desse vetor e um inteiro correpondente ao valor que deve ser localizado no
vetor. Se o elemento for encontrado a func¸a˜o retorna 1, sena˜o retorna 0. Utilize
o seguinte proto´tipo: int busca binaria(int [], int, int, int);
(16) Escreva uma func¸a˜o recursiva que ordene um vetor inteiro de forma na˜o
decrescente utilizando o algoritmo quicksort. A func¸a˜o deve receber um vetor
inteiro, um inteiro representando o indice do primeiro elemento desse vetor e um
inteiro representando o indice de seu u´ltimo elemento. A func¸a˜o deve modificar
o vetor recebido, e portanto na˜o sera´ necessa´rio retornar nenhum valor. Utilize
o seguinte proto´tipo: void quicksort(int [], int, int);
(17) Escreva uma func¸a˜o recursiva para calcular
(
n
k
)
, dado que
(
n
k
)
=
(
n−1
k
)
+
(
n−1
k−1
)
,(
m
m
)
= 1 e
(
m
1
)
= m. Sua func¸a˜o deve receber dois inteiros n e k, e deve retornar
um inteiro. Utilize o seguinte proto´tipo: int binomio(int, int);
(18) Escreva uma func¸a˜o recursiva para calcular a soma dos d´ıgitos de um inteiro
positivo. Por exemplo, a soma dos d´ıgitos de 345 e´ 12. Sua func¸a˜o recebe um
inteiro e retorna a respectiva soma, tambe´m no formato inteiro. Utilize o seguinte
proto´tipo: int digitos(int);
Pa´gina 2 de 3
Algoritmos e Programac¸a˜o (Prof. Marcelo S. Zanetti - DELC - CT - UFSM ): Lista 3
(19) Escreva uma func¸a˜o recursiva para determinar se os elementos de um ve-
tor inteiro formam um palindromo. Sua func¸a˜o recebe um vetor inteiro, um
inteiro representando o indice do primeiro elemento do referido vetor e um in-
teiro representando o indice do u´ltimo elemento do mesmo vetor. Exemplo,
v = [1, 20, 30, 20, 1] e´ palindromo (retornar 1) e w = [20, 30, 31, 20] na˜o e´ (retornar 0).
Utilize o seguinte proto´tipo: int palindromo(int [], int, int);
(20) Escreva uma func¸a˜o recursiva que resolva o problema “Torres de Hanoi”.
Inicialmente temos 5 discos de diaˆmetro diferentes na estaca A. O problema
consiste em mover os cinco discos da estaca A para C, utilizando a estaca B
como auxiliar. As regras sa˜o as seguintes:
• apenas o disco do topo de uma estaca pode ser movido
• nunca um disco de diaˆmetro maior pode ficar sobre um de diaˆmetro menor
Pa´gina 3 de 3