Recursividade

• Se um problema pode ser resolvido facilmente,
• resolva o problema;
• Se o problema é grande,
• elabore uma solução menor do problema,
• relacione com o problema maior,
• resolva o problema menor,
• volte ao problema inicial.

Motivação

• Um objeto é dito recursivo se ele consistir parcialmente ou for definido em termos de si mesmo.

​

• Uma função recursiva é uma função que faz uma chamada a si mesma.

Definição

Recursão Direta ou Indireta

• Se uma função A contiver uma chamada explícita a si mesma, essa função é dita diretamente recursiva.

A → A

• Se uma função A contiver uma chamada a uma função B, que por sua vez contenha uma chamada a função A, a função A é dita indiretamente recursiva.

A → B

B → A

• Todo problema recursivo deve ter
• Um caso base que pode ser resolvido diretamente;
• Um passo recursivo que envolve um problema menor.
• Caso base interrompe a recursão.
• Passos recursivos devem caminhar para caso base.

Recursão

Um exemplo

• Fatorial de um número.

1! = 1

​

2! = 2 * 1

​

3! = 3 * 2 *1

​

4! = 4 * 3 * 2 * 1

​

5! = 5 * 4 * 3 * 2 * 1

5!

Função recursiva

• Dado um problema:

​

• Subdivide este problema em problemas menores (mais simples) e chama a mesma função para resolvê-lo.

​

• Para de subdividir quando chega em um problema trivial.

Voltando ao exemplo

Valor Final = 120

Função Fatorial Recursiva

• Dado o problema do fatorial de um número:

​

n! = n * (n – 1)! para n>1

​

1! = 1

​

0! = 1

Implementando em Python

1 def fatorial(n):

2 if (n == 1) or (n == 0):

3 return 1

4 else:

5 return n * fatorial(n-1)

6 print(fatorial(5))

​

Chamadas recursivas

fat = fatorial(5)

Chamadas recursivas

fat = fatorial(5)

Chamadas recursivas

fat = fatorial(5)

Chamadas recursivas

fat = fatorial(5)

Chamadas recursivas

fat = fatorial(5)

Chamadas recursivas

fat = 120

fat = fatorial(5)

Teste de mesa da chamada recursiva

Main

Fat(5)

Fat(4)

Fat(3)

Fat(2)

Fat(1)

Exemplo

• Escreva uma função que recebe como parâmetro um inteiro positivo n e retorna a soma de todos os números inteiros entre 1 e n.

​

• n = 1 → soma(1) = 1
• n = 2 → soma(2) = 2 + soma(1)
• n = 3 → soma(3) = 3 + soma(2)

…

Genericamente: soma(n) = n + soma(n-1)

Caso base: soma(1) = 1

• Solução Recursiva:

def soma(n):

if (n == 1):

return 1

else:

return n + soma(n - 1)

Exemplo

• Chamada inicial para a função recursiva :

Exemplo

n = int(input("Qual o valor de n? "))

print ("O somatorio de 0 a %d :" % n)

print ("%d" % soma(n))

Exemplo

• Série de Fibonacci

Exemplo

​

def fibonacci(n):

if (n == 0) or (n == 1):

return n

else:

return fibonacci(n-1) + fibonacci(n-2)

fibonacci(4):

4

3

2

1

1

1

1

+

2

fibonacci(4): 3

0

+

0

1

+

1

2

1

0

+

0

1

3

fibonacci(4):

4

3

2

1

+

fibonacci(4): 3

0

+

1

+

2

1

0

+

1

0

1

1

2

1

0

1

3

• É melhor não usar recursão:
• Quando as chamadas recursivas acontecem apenas no início ou apenas no fim da função
• Motivo: cada chamada recursiva reserva memória para as variáveis locais e parâmetros
• Exemplos: as funções somatório e fatorial
• Quando o número de tarefas/cálculos repetidos é muito grande, a execução de um programa pode ficar inviável
• Motivo: em geral, cada chamada recursiva é independente da outra; se duas chamadas recursivas realizam os mesmos cálculos, esses cálculos serão repetidos
• Exemplo: a função recursiva para a série de Fibonacci

Recursão

Usando Depuração com Funções Recursivas

Usando Depuração com Funções Recursivas

Usando Depuração com Funções Recursivas

1. Escreva um programa que contenha uma função recursiva que calcule b^e, em que b e e são números inteiros positivos.
2. O produto entre dois números inteiros sempre pode ser calculado utilizando-se apenas o operador de adição.

Assim: 2 * 3 = 2 + 2 + 2

Ou seja: x * y = x + x + ...+ x (y vezes)

Escreva uma função recursiva para o cálculo do produto de dois números, usando apenas o operador de soma.

3. Escreva um programa que contenha uma função recursiva que receba um número natural n, e devolva a soma dos n primeiros números naturais ímpares.
4. Escreva um programa que leia dois números inteiros e divida um pelo outro, considerando sempre quociente e resto inteiros. A função deve retornar o valor do quociente, desprezando o resto.

​

Exercícios