Síntese e desafios: funções

Resumo

Esta aula encerra a quinta unidade do curso, dedicada às funções. Reconstrói a cadeia de conceitos que vai da declaração de uma função à recursão, passando pela pilha de chamadas, pelo contrato, pela passagem dos parâmetros, pelo escopo e pela duração das variáveis e pelo projeto por refinamento sucessivo; separa o que disso vale em qualquer linguagem do que é próprio de C++; reúne o comportamento indefinido da unidade, com o que o compilador adverte, o que o detector interrompe e o que ninguém assinala; repete em sua avaliação de saída as habilidades da avaliação de entrada; e termina com seis desafios que combinam a unidade inteira.

Objetivos de aprendizagem

Decompor um problema em funções, cada uma com sua interface e seu contrato (pré-condição e pós-condição), e testá-las separadamente.
Escolher o modo de passagem de cada parâmetro e a forma de devolver os resultados, e justificar a escolha.
Resolver um problema por recursão e provar sua correção por indução e sua terminação com uma medida que decresce, estimando seu custo em chamadas.
Reconhecer o comportamento indefinido da unidade (o caminho sem return, a referência pendente, o resultado que estoura, a pilha esgotada) e reescrever o programa sem ele.
Separar, no que se aprendeu na unidade, o que vale em qualquer linguagem do que é próprio de C++.

O que a unidade alcançou

A unidade propôs-se ensinar a decompor um problema em partes com nome, cada uma com uma interface e um contrato, e a resolver problemas por recursão. O propósito foi cumprido apoiando-se apenas no que a introdução declarou dar por sabido: os laços da unidade 4, com seu invariante e sua variante, a especificação da aula 1.1 e o modelo da memória da unidade 2. O programa dos números amigos, cujo laço copiado somava os divisores do número errado, escreve-se agora com uma só função, verificada uma vez contra o seu contrato.

Funções

A aula Funções ensinou a declarar, definir e chamar uma função, e separou três momentos: ao compilar, cada chamada é verificada contra uma declaração vista antes; ao ligar, busca-se a definição; ao executar, calculam-se os argumentos, cria-se um quadro na pilha de chamadas e o controle salta para o corpo. Mostrou que chegar ao final de uma função que não é void sem um return é comportamento indefinido, e fechou com o contrato, a pré-condição e a pós-condição, que reparte as responsabilidades entre quem chama e a função.

Parâmetros e escopo

A aula Parâmetros e escopo estudou por quais caminhos entram os dados e saem os resultados: o parâmetro por valor é uma cópia; o parâmetro por referência, um segundo nome para a posição de quem chama; a referência constante lê sem copiar. Disso se segue a regra de escolha (valor para o que é pequeno, referência constante para o que é grande e só se lê, referência apenas se modificar é o propósito) e, para vários resultados, std::pair e std::tuple com vinculações estruturadas. Distinguiu o escopo de um nome, propriedade do texto, da duração de uma variável, propriedade da execução, e terminou com a referência que sobrevive à sua posição.

Projetar com funções

A aula Projetar com funções ensinou a decidir que funções escrever, por refinamento sucessivo: um main breve que chama funções apenas declaradas e a descida a cada uma delas, de modo que a decomposição se desenha como uma árvore. Fixou os critérios de uma boa interface e a regra “uma função, uma tarefa”, com seus sinais (a conjunção no nome, a função que não cabe em uma tela, a flag) e os efeitos ocultos, como a variável global; apresentou a sobrecarga, com sua ordem de preferência e a chamada ambígua; e reescreveu os algoritmos da unidade 4 como funções testadas separadamente.

Recursão

A aula Recursão ensinou que uma função pode chamar a si mesma para resolver uma instância menor do problema. Provou a correção por indução, supondo correta a chamada menor, e a terminação com uma medida natural que decresce; seguiu com a pilha os quadros que se empilham e se desfazem, e mostrou como ela se esgota; advertiu que o tipo do resultado estoura muito antes que a pilha; e comparou Fibonacci recursivo e iterativo: $2\,692\,537$ chamadas contra 29 somas para $F_{30}$ .