Informática · 11.º Ano · Algoritmia e Estruturas de Dados Complexas · 1o Periodo

Introdução à Recursividade

Os alunos exploram o conceito de funções recursivas, identificando casos base e passos recursivos em problemas simples.

• Aprendizagens Essenciais
• DGE: Secundário - Pensamento Computacional
• DGE: Secundário - Algoritmia

Sobre este tópico

A recursividade é um dos conceitos mais elegantes e, simultaneamente, desafiantes do Pensamento Computacional no 11º ano. Este tópico foca-se na capacidade de uma função se invocar a si própria para resolver problemas que podem ser decompostos em instâncias menores do mesmo problema. No contexto das Aprendizagens Essenciais, exploramos não só a implementação técnica, mas também a análise crítica da eficiência, comparando soluções recursivas com abordagens iterativas.

Compreender a recursividade exige que os alunos visualizem o fluxo de execução e a gestão da pilha de memória (stack). É fundamental que identifiquem o caso base para evitar ciclos infinitos e que saibam avaliar quando a elegância do código recursivo compensa o custo computacional. Este tema prepara os alunos para estruturas de dados mais complexas, como árvores e grafos, que serão abordadas posteriormente.

Este tópico beneficia significativamente de abordagens centradas no aluno, onde a visualização física do empilhamento de chamadas ajuda a tornar concreto um conceito abstrato.

Questões-Chave

1. Como podemos decompor um problema complexo em subproblemas idênticos mais simples?
2. Diferencie a recursividade direta da indireta com exemplos práticos.
3. Analise a importância do caso base para evitar loops infinitos em funções recursivas.

Objetivos de Aprendizagem

• Identificar o caso base e o passo recursivo em funções recursivas simples.
• Explicar a diferença entre recursividade direta e indireta com exemplos de código.
• Analisar a necessidade do caso base para garantir a terminação de uma função recursiva.
• Comparar a complexidade de tempo de uma solução recursiva com uma solução iterativa equivalente para um problema dado.
• Criar uma função recursiva para resolver um problema de decomposição simples, como o cálculo do fatorial ou da sequência de Fibonacci.

Antes de Começar

Conceitos Fundamentais de Funções

Porquê: Os alunos precisam de compreender como definir, chamar e usar parâmetros em funções para poderem trabalhar com funções recursivas.

Estruturas de Controlo (Condicionais e Ciclos)

Porquê: A compreensão de `if-else` e `while`/`for` é crucial para identificar o caso base e o passo recursivo, e para comparar com abordagens iterativas.

Vocabulário-Chave

Recursividade	Uma técnica de programação onde uma função chama a si própria para resolver um problema, decompondo-o em subproblemas idênticos.
Caso Base	A condição numa função recursiva que impede a recursividade de continuar indefinidamente, fornecendo uma resposta direta para o subproblema mais simples.
Passo Recursivo	A parte da função recursiva onde a função chama a si própria com um argumento modificado, aproximando-se do caso base.
Chamada de Função	O ato de executar uma função, que, no caso da recursividade, pode incluir a própria função a ser chamada.
Pilha de Chamadas (Call Stack)	Uma estrutura de dados usada pelo runtime para gerir as chamadas de função, armazenando informações sobre cada chamada ativa, incluindo variáveis locais e o ponto de retorno.

Atenção a estes erros comuns

Erro comum

A recursividade é sempre mais eficiente do que a iteração por ser mais moderna.

O que ensinar em alternativa

Na realidade, a recursividade consome frequentemente mais memória devido à criação de novos frames na stack para cada chamada. É importante usar simulações de traçado de variáveis para mostrar o custo de memória associado a cada invocação.

Erro comum

Uma função recursiva corre para sempre se não tiver um 'break'.

O que ensinar em alternativa

Em programação, o conceito correto é o 'caso base'. Através da experimentação direta no IDE, os alunos percebem que, sem um caso base, o programa termina com um erro de sistema (stack overflow) e não apenas num ciclo infinito teórico.

Ideias de aprendizagem ativa

Simulação Física: A Pilha Humana

Os alunos representam instâncias de uma função recursiva (como o cálculo de um fatorial). Cada aluno recebe um papel com o valor de entrada, executa a lógica e 'passa a bola' ao colega seguinte, mantendo o estado em espera até que o caso base retorne o valor, ilustrando visualmente o funcionamento da stack.

45 min·Turma inteira

Círculo de Investigação: Recursividade vs Iteração

Em pequenos grupos, os alunos recebem dois algoritmos para o mesmo problema (ex: sequência de Fibonacci). Devem medir o tempo de execução para diferentes inputs e criar um pequeno relatório comparativo sobre o consumo de memória e velocidade, apresentando as conclusões à turma.

60 min·Pequenos grupos

Pensar-Partilhar-Apresentar: Caça ao Erro no Caso Base

O professor apresenta trechos de código recursivo com erros lógicos ou falta de caso base. Individualmente, os alunos identificam o problema; em pares, discutem a solução; e, finalmente, partilham com a turma como evitariam o estouro da pilha (stack overflow).

30 min·Pares

Ligações ao Mundo Real

• A exploração de estruturas de dados como árvores binárias de pesquisa, usadas em bases de dados e sistemas de ficheiros, frequentemente emprega algoritmos recursivos para percorrer e manipular os dados de forma eficiente. Profissionais de ciência de dados utilizam estas estruturas para otimizar consultas.
• Algoritmos de ordenação como Quicksort e Mergesort, essenciais para a gestão de grandes volumes de informação em sistemas de informação geográfica (SIG) ou em plataformas de e-commerce, baseiam-se na recursividade para dividir e conquistar conjuntos de dados.
• A modelação de fenómenos naturais complexos, como a ramificação de rios ou o crescimento de fractais em computação gráfica, pode ser representada através de funções recursivas, permitindo a geração de padrões detalhados e realistas.

Ideias de Avaliação

Bilhete de Saída

Apresente aos alunos o seguinte pseudocódigo: `funcao Exemplo(n): se n <= 1: retornar 1 senao: retornar n * Exemplo(n-1)`. Peça-lhes para identificar o caso base e o passo recursivo, e para prever o resultado de `Exemplo(3)`.

Verificação Rápida

Mostre aos alunos um exemplo de função recursiva (ex: cálculo do fatorial). Pergunte: 'O que aconteceria se o caso base fosse omitido? Como podemos garantir que a função termina?' Recolha respostas rápidas no quadro ou através de um formulário online.

Questão para Discussão

Coloque a questão: 'Quando é que uma solução recursiva é preferível a uma solução iterativa, mesmo que possa ser menos eficiente em termos de tempo ou memória?' Incentive os alunos a discutir a legibilidade do código, a semelhança com a definição matemática do problema e a complexidade de implementação.

Perguntas frequentes

Como explicar o conceito de caso base de forma simples?

O caso base é a condição de paragem que interrompe as chamadas sucessivas. Pode comparar-se a uma boneca Matrioshka: a recursividade é o ato de abrir bonecas sucessivamente, e o caso base é a boneca mais pequena que já não abre, permitindo-nos começar a fechar todas as outras.

Quais são os melhores exemplos práticos para ensinar recursividade?

O cálculo do fatorial, a sequência de Fibonacci, as Torres de Hanói e a exploração de diretórios num sistema de ficheiros são exemplos clássicos que permitem visualizar a decomposição do problema em subproblemas idênticos.

Quando é que um aluno deve optar por recursividade em vez de ciclos?

A escolha deve recair na recursividade quando a estrutura do problema é inerentemente recursiva (como navegar em árvores) ou quando a solução iterativa se torna excessivamente complexa e difícil de ler, priorizando a clareza do código.

Como é que a aprendizagem ativa ajuda a compreender a recursividade?

Estratégias como a simulação de papéis ou o traçado colaborativo de algoritmos permitem que os alunos 'vejam' a memória a ser ocupada. Ao discutirem em pares, conseguem verbalizar a lógica da auto-invocação, o que clarifica a confusão mental comum entre o fluxo sequencial e o fluxo recursivo.