3. Funções recursivas

Uma função pode chamar a si mesma e quando isso acontece, há uma fun­ção recursiva. O problema do fatorial é interessante para demonstrar o con­ceito de recursividade. É possível definir o fatorial de um número como sendo esse número multiplicado pelo fatorial de seu antecessor. Caso chamemos nosso número de n, temos uma definição recursiva do fatorial como:

Canva

 

Em Python, iríamos definir a função recursiva para cálculo do fatorial como:

 

# Programa 8.5 – Função recursiva do fatorial

def fatorial(n):
if n == 0 or n == 1:
return 1
else:
return n * fatorial(n - 1)

 

Acrescentaremos algumas linhas para facilitar o rastreamento, mudando o pro­grama para imprimir na entrada da função:

 

# Programa 8.6 – Função modificada para facilitar o rastreamento

def fatorial(n):
print(f"Calculando o fatorial de {n}")
if n == 0 or n == 1:
print(f"Fatorial de {n} = 1")
return 1
else:
fat = n * fatorial(n - 1)
print(f" fatorial de {n} = {fat}")
return fat
fatorial(4)

Que, como resultado, produz a tela para o cálculo do fatorial de 4:

 

Canva

 

A sequência de Fibonacci é outro problema clássico onde é possível aplicar funções recursivas. A sequência pode ser compreendida como o número de casais de coelhos que teríamos depois de cada ciclo de reprodução, levando em conta que cada ciclo dá origem a um casal. Vamos nos limitar à história dos casais de coelhos ainda que a sequência de Fibonacci revele matematicamente propriedades mais complexas.

 

A sequência inicia com dois números 0 e 1. Os próximos números são a soma dos dois anteriores. A sequência ficaria dessa forma: 0,1,1, 2, 3,5, 8,13, 21,…

 

Desse modo, uma função para calcular o enésimo termo da sequência de Fibonacci pode ser definida :

canva

 

Sendo implementada em Python como:

 

# Prograna 8.7 – Função recursiva de Fibonacci

def fibonacci(n):
if n <= 1:
return n
eise:
return fibonacci(n - 1) + fibonacci(n - 2)

 

Exercício 8.7. Defina uma função recursiva que calcule o maior divisor comum (M.D.C.) entre dois números a e b, em que a > b.

CODIGO

Em que ^LDJ pode ser escrito em Python como: a % b.

Exercício 8.8. Usando a função mdc definida no exercício passado, defina uma fun­ção para calcular o menor múltiplo comum (M.M.C.) entre dois números.

CODIGO

Em que |a * b pode ser escrito em Python como: abs(a * b).

Exercício 8.9. Rastreie o Programa 8.6 e contraponha o seu resultado com o apresentado.

Exercício 8.10. Reescreva a função para cálculo da sequência de Fibonacci, sem usar recursão.