Questão 66914

Uma professora de programação está ensinando o conceito de recursão para seus alunos do ensino médio. Ela percebe que, após aprenderem a mecânica da recursão, os alunos têm dificuldade em identificar quando um problema é um bom candidato para uma solução recursiva. Para desenvolver essa habilidade de 'pensar recursivamente', ela apresenta uma característica chave de problemas recursivos: a **auto-similaridade**. Ela explica: "Um problema tem auto-similaridade se ele pode ser decomposto em subproblemas que são versões menores do problema original. A solução para o problema original pode então ser construída a partir das soluções desses subproblemas. Pense em um fractal, como o Floco de Neve de Koch: cada lado do triângulo é substituído por uma forma que é, ela mesma, uma versão em miniatura do floco de neve inteiro. Essa é a essência da recursão: resolver um problema usando a solução para o mesmo problema em uma escala menor." Ela então propõe aos alunos que analisem quatro problemas diferentes e identifiquem qual deles exibe a propriedade de auto-similaridade mais clara, tornando-o um candidato ideal para uma solução recursiva.

Problema 1: Calcular a soma de todos os elementos de uma lista de números. Problema 2: Encontrar o maior elemento em uma lista de números. Problema 3: Calcular o fatorial de um número $n$ (n!). Problema 4: Verificar se um número é par ou ímpar.

Avaliando os problemas sob a ótica da auto-similaridade, analise as seguintes afirmações.

I. O Problema 3 (Fatorial) tem uma definição naturalmente recursiva: o fatorial de $n$ é $n$ vezes o fatorial de $n-1$. O problema de calcular `fatorial(n)` contém uma versão menor de si mesmo, `fatorial(n-1)`, exibindo uma clara auto-similaridade.

II. O Problema 1 (Soma da lista) também pode ser visto recursivamente: a soma de uma lista é o primeiro elemento mais a soma do resto da lista. O problema de somar uma lista de tamanho $n$ é decomposto em um problema de somar uma lista de tamanho $n-1$.

III. O Problema 4 (Par ou Ímpar) não é um bom candidato para recursão. Ele pode ser resolvido diretamente com uma única operação de módulo (`n % 2 == 0`), e não há uma maneira natural ou eficiente de decompô-lo em subproblemas auto-similares.

É correto o que se afirma em: