Programação

Aula 05 – Algoritmos e Funções Recursivas

Considere a definição da função fatorial:

n! = 1 se n 0

Considere agora a seguinte definição equivalente:

n! = 1 se n 0

Dizemos que essa última definição é uma definição recursiva, pois usa a função fatorial para definir a função fatorial. Note que chamando a função de f temos:

f(n) = 1 se n 0

A princípio parece estranho usar uma função para definir a si prórpia, mas vejamos como se calcula o fatorial usando a definição recursiva.

5!=5.4!=5.4.3!=5.4.3.2!=5.4.3.2.1!=5.4.3.2.1.0!=5.4.3.2.1.1 = 120

A definição acima faz sentido, pois tem uma regra de parada, isto é, tem um caso (n igual a zero) onde a função não é usada para calcular a si própria.

Muitas outras funções admitem definições recorrentes deste tipo, ou seja, usa-se a função para definir a si própria, com um caso particular não recorrente.

Funções recursivas em c

Já vimos que uma função em c pode chamar outras funções. Em particular pode chamar a si mesma. Quando isso ocorre dizemos que a função é recursiva.

A função fatorial pela definição recursiva acima ficaria:

int fatrec(int n) {if (n = 1)

Uma outra definição recursiva:

H(n) = 1 se n 1

Usando a definição recursiva acima:

H(4)=1/4+H(3)=1/4+1/3+H(2)=1/4+1/3+1/2+H(1)=1/4+1/3+1/2+1
Análogo ao fatorial, a função acima também tem o caso de parada (n igual a 1 ), onde o valor da função não é recorrente.

Portanto, usando a definição acima:

double harmrec(int n) {if (n == 1) return 1; return 1.0 / (double)n + harmrec(n-1); }

Para ilustrar o funcionamento de harmrec, veja o program abaixo, onde adicionamos um printf dentro de harmrec, para esclarecer qual a chamada em andamento:

P106) Dado n inteiro, calcular o número harmônico de ordem n, usando a função recursiva harmrec.

#include

double harmrec(int n) {printf("\nchamando harmrec