Trabalho Prático 2: Entendendo a Recursão

Curso de Engenharia de Computação
Laboratório de AEDS1 - 2014/1
Trabalho Prático 2: Entendendo a Recursão

Este trabalho tem o objetivo de auxiliar o entendimento da recursão em programação. Aspectos da dinâmica da recursão e seus custos são investigados. Cada exercício a seguir tem duas partes. A primeira parte consiste implementar a função recursiva citada e inserir código para mostrar sua execução, por meio de impressões bem planejadas e elaboradas, para valores pequenos dos parâmetros. O desenho produzido pela impressão da execução – mostrando o desenvolvimento da recursão e o valor das variáveis e parâmetros – deve ser capaz de ajudá-lo a explicar como funciona a função recursiva. Seja criativo, criterioso e organizado. A impressão gerada em cada caso deve caber em uma página. A segunda parte de cada exercício visa medir os custos e o tempo de execução de cada função.
Primeiro exercício: implemente a função recursiva para o cálculo do fatorial.
a) Insira código de impressão em locais apropriados na função para mostrar sua execução para valores pequenos. Imprima o número da chamada recursiva e o valor do parâmetro.
b) Verifique qual é o maior número para o qual você consegue calcular o valor do seu fatorial usando sua função. Escolha os tipos de dados adequados para números grandes. Use a biblioteca limits.h para ver os limites de cada tipo definido na linguagem C.
Segundo exercício: implemente a função recursiva para o cálculo da série de Fibonacci.
a) Insira código de impressão em locais apropriados na função para mostrar sua execução para um valor pequeno da série, maior do que 6. Mostre todas as chamadas recursivas e seus parâmetros. Teste várias opções de impressão antes de escolher uma.
b) Apresente uma tabela mostrando o número de somas e o tempo de execução gasto pela função recursiva para o cálculo da série de Fibonacci, para n crescente, onde n é o termo da série. Terceiro exercício: considere a seguinte função recursiva de