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 0 e têm um tamanho n.
  • Para as operações com inteiros, é necessário decidir casos com sinais e divisão por zero; vou explicar a versão para b\neq0 e tratar o caso de divisores negativos usando o valor absoluto de b.
  • 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:
    1. Caso base: um caso simples que pode ser respondido sem chamadas recursivas (ex.: vetor vazio, tamanho 1, número menor que divisor).
    2. Passo recursivo: como reduzir o problema para uma versão menor (ex.: considerar os primeiros n-1 elementos).
  • Exemplo simples para fixar a ideia: somar os primeiros n números de um vetor v.
    • Caso base: se n=0 então \text{Sum}(v,0)=0.
    • Passo: \text{Sum}(v,n)=\text{Sum}(v,n-1)+v[n-1].
    • A cada chamada reduzimos n até chegar a 0.
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 \text{mean}(v) para um vetor v de tamanho n.
  • Estratégia mais simples e prática para prova: calcular a soma recursivamente e depois dividir por n.
    • Definir \text{Sum}(v,n) = soma dos primeiros n elementos de v.
    • Caso base: se n=0 então \text{Sum}(v,0)=0.
    • Passo recursivo: para n>0, \text{Sum}(v,n)=\text{Sum}(v,n-1)+v[n-1].
    • Depois, \text{mean}(v)=\dfrac{\text{Sum}(v,n)}{n} (assumindo n>0; para n=0 a média não está definida).
  • Exemplo concreto passo a passo: v=[2,5,3], n=3.
    • \text{Sum}(v,0)=0.
    • \text{Sum}(v,1)=\text{Sum}(v,0)+v[0]=0+2=2.
    • \text{Sum}(v,2)=\text{Sum}(v,1)+v[1]=2+5=7.
    • \text{Sum}(v,3)=\text{Sum}(v,2)+v[2]=7+3=10.
    • \text{mean}(v)=\dfrac{10}{3}.
  • 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 n.

Passo 4

Maior elemento de um vetor — ideia e desenvolvimento passo a passo:
  • Objetivo: \text{Max}(v,n)\) = maior elemento entre os primeiros \(n\) elementos de \(v\). - Caso base: se \(n=1\) então \(\text{Max}(v,1)=v[0]\). - Passo recursivo: para \(n>1\), 1. Calcular \(m=\text{Max}(v,n-1)\) — maior entre os primeiros \(n-1\) elementos. 2. Comparar \(m\) com \(v[n-1]\) e retornar o maior: \[\text{Max}(v,n)= \begin{cases} m, & \text{se } m\ge v[n-1],\\[4pt] v[n-1], & \text{se } v[n-1]>m. \end{cases}
  • Exemplo passo a passo: v=[4,1,7,3]\], \(n=4.
    • \text{Max}(v,1)=4.
    • \text{Max}(v,2)=\max(4,1)=4.
    • \text{Max}(v,3)=\max(4,7)=7.
    • \text{Max}(v,4)=\max(7,3)=7.
  • Dica: para implementar na prova, use a comparação direta; evita passar fatias do vetor (se a linguagem permitir, passe índice n para controlar o tamanho considerado).]

Passo 5

Resto da divisão por subtração — conceito, casos e recursão:
  • Objetivo: dado a e b inteiros, calcular o resto r da divisão de a por b usando somente subtrações repetidas.
  • Observações importantes e suposições:
    • Divisão por zero não é definida; portanto se b=0 a função deve tratar como erro.
    • Para evitar ambiguidades com sinal, é comum definir o resto com 0\le r<|b|. Vou adotar essa convenção: o resto será não-negativo e menor que |b|.
    • Procedimento: trabalhar com os valores absolutos para o divisor e para o dividendo; o resultado final será o resto não-negativo.
  • Estratégia e formulação recursiva (assumindo |b|>0):
    1. Seja B=|b| e A=|a|.
    2. Caso base: se A<B então \text{Resto}(A,B)=A.
    3. Passo recursivo: se A\ge B então \text{Resto}(A,B)=\text{Resto}(A-B,B).
    4. Ao final, retornar \text{Resto}(|a|,|b|). (Isso garante 0\le r<|b|.)
  • Exemplo com números: \text{Resto}(23,5).
    • 23\ge5\Rightarrow\text{Resto}(23,5)=\text{Resto}(18,5)=\text{Resto}(13,5)=\text{Resto}(8,5)=\text{Resto}(3,5)=3.
  • Comentário sobre sinais: se o problema exigir resto com sinal do dividendo (comum em algumas linguagens), ajustar depois: se a<0 e quiser resto negativo, retornar -r. Mas a versão padrão matemática retorna r\ge0.

Passo 6

Tamanho de uma cadeia de caracteres — ideia recursiva e exemplos:
  • Objetivo: \text{Len}(s) = número de caracteres da cadeia s.
  • Caso base: se s é a cadeia vazia (denotada por \varepsilon ou \text{""}) então \text{Len}(s)=0.
  • Passo recursivo: se s não é vazia, escreva s como c\cdot t onde c é o primeiro caractere e t é a cauda (resto da cadeia). Então \text{Len}(s)=1+\text{Len}(t).
  • Exemplo: s=\text{"ola"}.
    • \text{Len}(\text{"ola"})=1+\text{Len}(\text{"la"})=1+1+\text{Len}(\text{"a"})=1+1+1+\text{Len}(\text{""})=3.

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) / n
    
    Explicação: Sum reduz n até 0 somando o último elemento v[n-1] em cada passo; Mean só 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 primeiros n-1 elementos 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: RestoAbs subtrai repetidamente B de A até A < B. Resto cuida de sinais e devolve o resto no intervalo [0,|b|).
  • 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 soma 1 a 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 \text{Sum} ou \text{RestoAbs}) 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 1, vetor vazio (onde aplicável), divisor igual a 1, 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:])

Exercícios relacionados