Programação

Recursão e algoritmos recursivos
Muitos problemas têm a seguinte propriedade: cada instância do problema contém uma instância menor do mesmo problema. Dizemos que esses problemas têm estrutura recursiva. Para resolver um tal problema podemos aplicar o seguinte método:
• •

se a instância em questão é pequena, 1. resolva-a diretamente (use força bruta se necessário); senão, 1. reduza-a a uma instância menor do mesmo problema, 2. aplique o método à instância menor e 3. volte à instância original.

Para que uma função recursiva seja compreensível, é muito importante que o autor da função diga, explicitamente, o que a função faz. Portanto, eu deveria escrever o seguinte comentário antes do código: 1. Dada a definição de fatorial: x! = x * (x-1)! 0! = 1 Faça uma função recursiva para o calculo do fatorial de números inteiros positivos. 2. Qual o resultado da execução do programa abaixo? int ff (int n) { if (n == 1) return 1; if (n % 2 == 0) return ff (n/2); return ff ((n-1)/2) + ff ((n+1)/2); } int main (void) { printf ("%d", ff (7)); return 0; }

3. FIBONACCI. A função de Fibonacci é definida por: F (0) = 0, F (1) = 1 e F (n) = F(n-1) + F(n-2) para n > 1. Descreva a função F em linguagem C. Faça uma versão uma recursiva. 4. Seja F a versão recursiva da função de Fibonacci. O cálculo do valor da expressão F(3) provocará a seguinte sequência de invocações da função: F(3) F(2) F(1) F(0) F(1)

Qual a sequência de invocações da função provocada por F(5)? 5. Implemente um algoritmo recursivo para imprimir os elementos de uma lista dinâmica encadeada.