Aula Prática 5
Recursão
Monitoria 2011.2

Na linguagem C, como em muitas
outras linguagens, uma função pode
chamar a si própria.
 Uma
função assim é chamada função
recursiva.
CUIDADO!

Todo cuidado é pouco ao se fazer funções
recursivas. A primeira coisa a se providenciar
é um critério de parada.

Este vai determinar quando a função deverá
parar de chamar a si mesma.

Isto impede que a função se chame infinitas
vezes.
Estrutura Básica
tipo funcao(parametros)
{
tipo retorno;
if(Condição de parada)
{
...
}
else //recursão
{
// atribuição não é obrigatória
retorno = funcao(parametrosNovos);
}
return retorno;
}
Exemplo

Uma função que calcule o fatorial de um número
inteiro n é um bom exemplo de uma função
recursiva:

Note que, enquanto n não menor ou igual
a 1, a função fat chama a si mesma,
cada vez com um valor menor. N<=1 é
critério de parada para esta função.
Vantagens da Recursão

Solução mais simples de alguns
problemas;

Em geral, códigos mais concisos;

Caso não seja usada, é necessário
manter o controle das variáveis
manualmente (book keeping)
Desvantagens da Recursão

Funções recursivas são mais lentas
que funções iterativas, pois muitas
chamadas consecutivas a funções são
feitas;

Erros de implementação podem levar a
chamadas infinitas. Isto é, caso não seja
indicada uma condição de parada, ou
se esta condição nunca for satisfeita,
entre outros.
DÚVIDAS?
Exercícios

Faça um programa que receba dois números e um tipo de
operação (+, -, /, *). Encontre o valor de cada um
desses números através de uma função recursiva mostrada
abaixo, depois realize a operação informada pelo usuário entre os
dois novos números.
F(x) = x + (x-2) + (x-4) + (x-6) + .... + 1, Parando em 1 ou 0.
Ex:
x=4 e y =3
operacao = *
F(4) = 4 + 2 + 0 = 6
F(3) = 3 + 1 = 4
Saida = 6 * 4 = 24
Exercícios

Faça um programa que calcule
recursivamente a soma dos digitos de um
inteiro positivo.
Ex:
x = 1324.
Resultado = 1+3+2+4 = 10
Exercícios
A conjectura de collatz estabelece uma seqüência de números, ou
trajetória, que a partir de um número natural inicial obedece aos seguintes
critérios:
 1. Se o número for par seu sucessor na seqüência será sua metade
 2. Se o número for ímpar seu sucessor será uma unidade superior ao seu
triplo.
 A conjectura diz que toda sequencia terminará em 1.
Imprima a sequencia de numeros de forma que o primeiro número será o
digitado pelo usuário e o último será o numero 1.
 Obs: Suponha que 0 < n <= 100.
