recursividade

INF1007: Programação 2

4 - Funções Recursivas

12/03/2014

(c) Dept. Informática - PUC-Rio

1

Tópicos Principais
• Recursão
• Definições recursivas

• Funções Recursivas
• Implementação

• Comportamento

12/03/2014

(c) Dept. Informática - PUC-Rio

2

Definições Recursivas
• Em uma definição recursiva um item é definido em termos de si mesmo, ou seja, o item que está sendo definido aparece como parte da definição;
• Em todas as funções recursivas existe:
– Caso base (um ou mais) cujo resultado é imediatamente conhecido. – Passo recursivo em que se tenta resolver um sub-problema do problema inicial.

12/03/2014

(c) Dept. Informática - PUC-Rio

3

Definições Recursivas
• Exemplo: o fatorial de um número

Caso BASE

1,sen  0 n! n  (n  1)!,sen  0
Passo
Recursivo

12/03/2014

(c) Dept. Informática - PUC-Rio

4

Definições Recursivas
• Exercício: forneça a definição recursiva para a operação de potenciação
Caso BASE

1, se n  0 x  x  x ( n1) , se n  0

n

Passo
Recursivo

12/03/2014

(c) Dept. Informática - PUC-Rio

5

Funções Recursivas
• Definição:
– Uma função recursiva é aquela que faz uma chamada para si mesma. Essa chamada pode ser:
•

direta: uma função A chama a ela própria

•

indireta: função A chama uma função B que, por sua vez, chama
A

/* Recursao direta */ void func_rec(int n)
{
... func_rec(n-1); ...
}
12/03/2014

(c) Dept. Informática - PUC-Rio

6

Funções Recursivas
• Exemplo: função recursiva para cálculo de fatorial
1, se n  0 n! 
n  (n  1)!, se n  0
/* Função recursiva para cálculo do fatorial */ int fat (int n)
{
Caso BASE if (n==0) return 1; else Passo return n*fat(n-1);
Recursivo
}

12/03/2014

(c) Dept. Informática - PUC-Rio

7

Funções Recursivas
• Exemplo: função recursiva para cálculo de potenci ação

/* Função recursiva para cálculo de potenciacao */ int pot (int x, int n)
{