Aplicações Informáticas B · 12.º Ano · Algoritmia e Estruturas de Dados · 1o Periodo

Recursividade

Os alunos exploram o conceito de recursividade e a sua aplicação na resolução de problemas que podem ser divididos em subproblemas semelhantes.

• Aprendizagens Essenciais
• DGE: Secundário - Algoritmia e Programação
• DGE: Secundário - Pensamento Computacional

Sobre este tópico

A recursividade permite resolver problemas dividindo-os em subproblemas semelhantes ao original, com uma função a chamar-se a si própria até atingir uma condição base. No 12.º ano, os alunos comparam implementações recursivas e iterativas, como no cálculo do fatorial ou da sequência de Fibonacci, e analisam riscos como a pilha de chamadas transbordar sem condição de paragem adequada. Esta abordagem simplifica a lógica em problemas de divide-and-conquer, como percorrer árvores ou grafos.

No currículo de Algoritmia e Estruturas de Dados, a recursividade fortalece o pensamento computacional, promovendo decomposição e padrões. Os alunos exploram como uma solução recursiva pode ser mais elegante, embora exija controlo de profundidade para evitar loops infinitos. Ligada aos standards da DGE para programação secundária, esta unidade prepara para algoritmos avançados.

A aprendizagem ativa beneficia este tema porque conceitos abstractos como pilha de chamadas e condições base tornam-se concretos através de codificação prática, depuração colaborativa e visualizações de árvores de recursão. Os alunos ganham confiança ao verem execuções passo a passo, distinguindo recursão de iteração na prática.

Questões-Chave

1. Compare a implementação de soluções recursivas e iterativas para o mesmo problema.
2. Analise os riscos de uma função recursiva sem uma condição de paragem adequada.
3. Explique como a recursividade pode simplificar a lógica de certos algoritmos.

Objetivos de Aprendizagem

• Comparar a complexidade temporal e espacial de algoritmos recursivos e iterativos para problemas como o cálculo do fatorial e a sequência de Fibonacci.
• Analisar os efeitos de uma condição de paragem inadequada numa função recursiva, prevendo cenários de erro como o transbordo da pilha de chamadas.
• Explicar como a recursividade simplifica a implementação de algoritmos de 'dividir e conquistar', como a ordenação por fusão (merge sort).
• Criar uma função recursiva para resolver um problema específico, como a geração de combinações ou permutações, demonstrando a aplicação de casos base e passos recursivos.

Antes de Começar

Introdução à Programação e Variáveis

Porquê: Os alunos precisam de compreender o conceito básico de variáveis e como elas armazenam e manipulam dados para poderem seguir o fluxo de execução de uma função.

Estruturas de Controlo: Condicionais (if/else)

Porquê: A identificação e implementação do caso base numa função recursiva dependem diretamente da compreensão de estruturas condicionais.

Estruturas de Controlo: Ciclos (for, while)

Porquê: A comparação entre soluções recursivas e iterativas requer que os alunos já dominem a lógica de repetição proporcionada pelos ciclos.

Vocabulário-Chave

Recursividade	Uma técnica de programação onde uma função chama a si própria para resolver um problema, dividindo-o em instâncias mais pequenas do mesmo problema.
Caso Base	A condição numa função recursiva que termina a recursão, evitando chamadas infinitas. É a solução mais simples do problema.
Passo Recursivo	A parte de uma função recursiva onde a função chama a si própria com um argumento modificado, aproximando-se do caso base.
Pilha de Chamadas	Uma estrutura de dados que regista as chamadas ativas de funções. Na recursividade, cada chamada de função adiciona um quadro à pilha, e cada retorno remove um.
Profundidade de Recursão	O número máximo de chamadas recursivas que podem ocorrer simultaneamente antes de a pilha de chamadas transbordar.

Atenção a estes erros comuns

Erro comum

A recursão é sempre mais lenta que a iteração.

O que ensinar em alternativa

Embora recursão pura gere mais chamadas, como em Fibonacci sem memoização, optimizações igualam ou superam iterações em certos casos. Actividades de comparação cronometrada ajudam alunos a medir empiricamente, ajustando crenças baseadas em dados reais.

Erro comum

Qualquer problema iterativo pode ser recursivo sem alterações.

O que ensinar em alternativa

Muitos problemas requerem reformulação para subproblemas idênticos. Discussões em grupo sobre fatorial revelam que condições base são cruciais, e depuração activa corrige ideias erradas ao mostrar falhas concretas.

Erro comum

Recursão infinita ocorre por acaso, sem relação com código.

O que ensinar em alternativa

Falta de base causa stack overflow previsível. Simulações passo a passo em pares fazem alunos preverem e observarem o erro, reforçando a importância de condições de paragem através de experiência directa.

Ideias de aprendizagem ativa

Comparação em Pares: Fatorial Recursivo vs Iterativo

Os alunos implementam o fatorial em Python de forma recursiva e iterativa. Em seguida, cronometram execuções para n=10, 20, 30 e comparam eficiência. Discutem vantagens em cada abordagem.

30 min·Pares

Pequenos Grupos: Torres de Hanói Simuladas

Grupos constroem uma versão recursiva das Torres de Hanói para 3 discos, usando pilhas para simular movimentos. Registam o número de chamadas recursivas e verificam a solução ótima. Apresentam o código à turma.

45 min·Pequenos grupos

Aula Inteira: Árvore de Recursão Fibonacci

A turma traça colectivamente a árvore de chamadas para Fibonacci(5) num quadro. Depois, codificam e executam com depurador, contando chamadas redundantes. Discutem memoização como optimização.

35 min·Turma inteira

Individual: Depuração de Recursão Infinita

Cada aluno recebe uma função recursiva sem base e identifica o erro. Adicionam a condição e testam com inputs variados, registando o número máximo de chamadas antes do crash.

20 min·Individual

Ligações ao Mundo Real

• A recursividade é fundamental na computação gráfica para gerar fractais, como os usados em paisagens de videojogos ou efeitos visuais em filmes, onde padrões complexos são criados a partir de repetições simples de formas geométricas.
• Em sistemas de gestão de bases de dados, a recursividade pode ser utilizada para consultar dados hierárquicos, como organogramas de empresas ou estruturas de ficheiros em sistemas operativos, permitindo percorrer relações complexas de forma eficiente.
• Algoritmos de inteligência artificial, como os usados em motores de busca ou sistemas de recomendação, empregam recursividade para explorar espaços de estados ou construir modelos preditivos, dividindo problemas de decisão complexos em subproblemas mais tratáveis.

Ideias de Avaliação

Bilhete de Saída

Apresente aos alunos o código de uma função recursiva simples (ex: cálculo do fatorial) e uma versão iterativa. Peça-lhes para escreverem num pequeno papel: 1) Qual a principal diferença entre as duas implementações? 2) Qual o risco associado à função recursiva se o caso base for omitido?

Verificação Rápida

Durante a aula, apresente um problema simples (ex: contar o número de nós numa árvore binária pequena). Peça aos alunos para, em pares, esboçarem rapidamente a lógica de uma solução recursiva, identificando o caso base e o passo recursivo. Circule pela sala para verificar a compreensão.

Questão para Discussão

Inicie uma discussão em grupo com a seguinte questão: 'Em que situações a elegância de uma solução recursiva pode não compensar a potencial sobrecarga de memória ou o risco de erros associados à pilha de chamadas? Dê exemplos concretos.'

Perguntas frequentes

Como comparar soluções recursivas e iterativas?

Implemente ambas para o mesmo problema, como fatorial, e compare legibilidade, eficiência e uso de memória com testes cronometrados. A recursiva destaca-se em lógica simples para divide-and-conquer, mas iteração poupa recursos em loops lineares. Atividades práticas revelam trade-offs reais, ajudando alunos a escolherem adequadamente em contextos variados.

Quais os riscos de recursão sem condição de paragem?

Sem base, ocorrem chamadas infinitas, esgotando a pilha e causando crash. Alunos devem sempre incluir if para casos triviais, como n=0 ou n=1. Testes com depuradores mostram o overflow, ensinando controlo rigoroso e análise prévia de profundidade máxima.

Como a recursividade simplifica algoritmos?

Reduz código repetitivo em problemas fractais ou hierárquicos, como percorrer árvores binárias. Em vez de loops aninhados, uma chamada recursiva lida com subestruturas idênticas. Exemplos como soma de listas ligadas mostram elegância, mas requerem prática para evitar ineficiências ocultas.

Como a aprendizagem ativa ajuda a compreender recursividade?

Actividades como traçar árvores de chamadas em grupo ou depurar funções em pares tornam abstracto concreto, visualizando pilha e base. Codificação colaborativa revela erros comuns, como falta de paragem, enquanto simulações de Torres de Hanói constroem intuição para divide-and-conquer. Estes métodos aumentam retenção e confiança em programação avançada.