Escreva funções recursivas para calcular:
- a média dos elementos de um vetor;
- o maior elemento de um vetor;
- o resto da divisão entre dois números inteiros (utilizando somente subtrações) e
- o tamanho de uma cadeia de caracteres.
Passo 1
O que nos pedem (lista clara das quatro tarefas):
- Escrever uma função recursiva para calcular a média dos elementos de um vetor.
- Escrever uma função recursiva para encontrar o maior elemento de um vetor.
- Escrever uma função recursiva para calcular o resto da divisão entre dois inteiros usando somente subtrações.
- Escrever uma função recursiva para calcular o tamanho de uma cadeia de caracteres.
Informações relevantes dadas (o que podemos assumir para resolver):
- Os vetores são indexáveis por posição começando em
e têm um tamanho . - Para as operações com inteiros, é necessário decidir casos com sinais e divisão por zero; vou explicar a versão para
e tratar o caso de divisores negativos usando o valor absoluto de . - Para a cadeia de caracteres, assume-se que existe uma operação para obter a “cauda” da cadeia (todos os caracteres exceto o primeiro) e verificar se a cadeia está vazia.
- O enunciado não exige uma linguagem específica; darei pseudocódigo claro e também exemplos em estilo Python para facilitar a leitura.
Passo 2
Conceito e estratégia geral (mini-aula sobre recursão, bem mastigada e com exemplos):
- Recursão é quando uma função chama a si mesma para resolver um subproblema menor até atingir um caso simples (caso base).
- Dois ingredientes importantes em qualquer função recursiva:
- Caso base: um caso simples que pode ser respondido sem chamadas recursivas (ex.: vetor vazio, tamanho
, número menor que divisor). - Passo recursivo: como reduzir o problema para uma versão menor (ex.: considerar os primeiros
elementos).
- Caso base: um caso simples que pode ser respondido sem chamadas recursivas (ex.: vetor vazio, tamanho
- Exemplo simples para fixar a ideia: somar os primeiros
números de um vetor . - Caso base: se
então . - Passo:
. - A cada chamada reduzimos
até chegar a .
- Caso base: se
Vou seguir essa mesma lógica para cada item pedido: identificar um caso base claro e uma redução que diminua o tamanho do problema.
Passo 3
Média dos elementos de um vetor — ideia e passo a passo didático:
- Objetivo: calcular
para um vetor de tamanho . - Estratégia mais simples e prática para prova: calcular a soma recursivamente e depois dividir por
. - Definir
= soma dos primeiros elementos de . - Caso base: se
então . - Passo recursivo: para
, - Depois,
(assumindo ; para a média não está definida).
- Definir
- Exemplo concreto passo a passo:
, . -
. -
. -
. -
. -
.
-
- Observação prática para prova: se pedirem só a média, escrever a função recursiva para a soma e depois uma função wrapper que divide por
.
Passo 4
Maior elemento de um vetor — ideia e desenvolvimento passo a passo:
- Objetivo:
- Exemplo passo a passo:
.
-
. -
. -
. -
.
-
- Dica: para implementar na prova, use a comparação direta; evita passar fatias do vetor (se a linguagem permitir, passe índice
para controlar o tamanho considerado).]
Passo 5
Resto da divisão por subtração — conceito, casos e recursão:
- Objetivo: dado
e inteiros, calcular o resto da divisão de por usando somente subtrações repetidas. - Observações importantes e suposições:
- Divisão por zero não é definida; portanto se
a função deve tratar como erro. - Para evitar ambiguidades com sinal, é comum definir o resto com
. Vou adotar essa convenção: o resto será não-negativo e menor que . - Procedimento: trabalhar com os valores absolutos para o divisor e para o dividendo; o resultado final será o resto não-negativo.
- Divisão por zero não é definida; portanto se
- Estratégia e formulação recursiva (assumindo
): - Seja
e . - Caso base: se
então . - Passo recursivo: se
então - Ao final, retornar
. (Isso garante .)
- Seja
- Exemplo com números:
. -
.
-
- Comentário sobre sinais: se o problema exigir resto com sinal do dividendo (comum em algumas linguagens), ajustar depois: se
e quiser resto negativo, retornar . Mas a versão padrão matemática retorna .
Passo 6
Tamanho de uma cadeia de caracteres — ideia recursiva e exemplos:
- Objetivo:
= número de caracteres da cadeia . - Caso base: se
é a cadeia vazia (denotada por ou ) então . - Passo recursivo: se
não é vazia, escreva como onde é o primeiro caractere e é a cauda (resto da cadeia). Então - Exemplo:
. -
.
-
Passo 7
Implementações em pseudocódigo (claro para aplicar em prova) e explicação rápida de cada função
-
Média usando soma recursiva:
Pseudocódigo:function Sum(v, n): if n = 0: return 0 else: return Sum(v, n-1) + v[n-1] function Mean(v, n): if n = 0: error "média indefinida para n=0" return Sum(v, n) / nExplicação:Sumreduznaté0somando o último elementov[n-1]em cada passo;Meansó divide a soma pelo tamanho. -
Maior elemento:
Pseudocódigo:function Max(v, n): if n = 1: return v[0] else: m = Max(v, n-1) if m >= v[n-1]: return m else: return v[n-1]Explicação: sempre reduz o problema ao máximo dos primeirosn-1elementos e compara com o novo elemento. -
Resto usando subtrações (resto não-negativo menor que |b|):
Pseudocódigo:function RestoAbs(A, B): // A >= 0, B > 0 if A < B: return A else: return RestoAbs(A - B, B) function Resto(a, b): // lida com sinais e b != 0 if b = 0: error "divisão por zero" B = abs(b) A = abs(a) return RestoAbs(A, B)Explicação:RestoAbssubtrai repetidamenteBdeAatéA < B.Restocuida de sinais e devolve o resto no intervalo. -
Comprimento (tamanho) de uma string:
Pseudocódigo:function Len(s): if s == "": return 0 else: return 1 + Len(s[1:]) // s[1:] é a cauda (string sem o primeiro caractere)Explicação: reduz a string retirando o primeiro caractere e soma1a cada chamada até a string ficar vazia.
Passo 8
Notas finais de prova (dicas práticas e casos de canto):
- Sempre identifique claramente o caso base; sem ele a recursão diverge.
- Em provas, se for permitido, é aceitável definir uma função auxiliar (como
ou ) para separar preocupações (por exemplo, tratar sinais). - Para vetores grandes, recursão pode estourar pilha; em prova isso normalmente não importa, mas na implementação prática prefira laços se for requisito de eficiência.
- Teste mentalmente com vetores pequenos e com casos limites: vetor de tamanho
, vetor vazio (onde aplicável), divisor igual a , divisor maior que o dividendo, strings vazias.
Resposta
function Mean(v, n): return Sum(v,n)/n where Sum(v,0)=0 and Sum(v,n)=Sum(v,n-1)+v[n-1] for n>0
function Max(v, n): if n=1 then return v[0] else m=Max(v,n-1); return m if m>=v[n-1] else return v[n-1]
function Resto(a, b): if b=0 error; return RestoAbs(abs(a), abs(b)) where RestoAbs(A,B)=A if A<B else RestoAbs(A-B,B)
function Len(s): return 0 if s=="" else return 1+Len(s[1:])
function Max(v, n): if n=1 then return v[0] else m=Max(v,n-1); return m if m>=v[n-1] else return v[n-1]
function Resto(a, b): if b=0 error; return RestoAbs(abs(a), abs(b)) where RestoAbs(A,B)=A if A<B else RestoAbs(A-B,B)
function Len(s): return 0 if s=="" else return 1+Len(s[1:])