Enviar um café pro programador

Pode me ajudar a transformar cafeína em código?

Funções recursivas: pra aprender recursividade, tem que saber recursividade

O título desse artigo em C pode parecer estranho, à primeira vista, mas ao fim do tutorial você entenderá essa ‘piada interna’ entre os programadores.

Neste tutorial de nossa apostila de C, vamos ensinar uma importante técnica: a recursão.

Recursividade em C

Uma função que é dita recursiva é aquela que invoca ela mesma.
Já explicamos, e demos exemplos, que é possível, recomendável e normal que uma função invoque outra.

Porém também é possível que uma função chame ela mesma, mas é preciso um cuidado especial para não cairmos em um looping infinito.

Geralmente, para que uma função não fique invocando ela mesma indefinidamente, devemos fazer umas alterações no argumento, ao invocar novamente a função ao passo que devemos definir, na função, testes condicionais sobre o parâmetro para saber onde devemos parar de invocar a função.

Ok, a equipe do curso C Progressivo assume: essa explicação é realmente complicada e todos sentiram dificuldade a primeira vez que a leram.

Mas, como de costume, vamos apresentar diversos exemplos de códigos, bem comentados, para que você possa entender melhor isso na prática.


Exemplo de código usando Recursão

Crie um programa em C que peça um número inteiro ao usuário e retorne a soma de todos os números de 1 até o número que o usuário introduziu ou seja: 1 + 2 + 3 + ... + n
Utilize recursividade.

Vamos criar uma função soma(int n).
Se n=5, essa função deve retornar: soma(5) = 5 + 4 + 3 + 2 + 1
Se n=4, essa função deve retornar: soma(4) = 4 + 3 + 2 + 1
Se n=3, essa função deve retornar: soma(3) = 3 + 2 + 1

E assim por diante. Porém, para fazermos uso da brilhante idéia matemática da recursividade, temos que notar padrões.
Veja que:
soma(5) = 5 + 4 + 3 + 2 +1 = 5 + soma(4)

O mesmo para:
soma(4) = 4 + 3 + 2 + 1 = 4 + soma(3)

Ou seja, temos a fórmula geral:
soma(n) = n + soma(n-1)
Concorda?

Ou seja:
soma(n) = n + soma(n-1) = n + (n-1) + soma(n-2) = n + (n-1) + (n-2) + soma(n-3)...

E onde essa soma para? Para quando o último elemento dessa soma for 1.
Então:
soma(n) = n +(n-1) + (n-2) + (n-3) + .... + 1

Agora vamos traduzir essa fórmula em termos de programação.
A função recebe um número, e a primeira coisa que ela deve fazer é ver se esse valor é 1.
Se for, deve retornar 1, afinal:
soma(1) = 1

E se não for 1, deve retornar:
n + soma(n-1)

Isso é feito da uma maneira muito simples, através de um simples teste condicional do tipo IF ELSE.
Veja como ficou nosso código em C:

#include <stdio.h>
 
int soma(int n)
{
    if(n == 1)
        return 1;
    else
        return ( n + soma(n-1) );
}
 
int main()
{
    int n;
    printf("Digite um inteiro positivo: ");
    scanf("%d", &n);
 
    printf("Soma: %d\n", soma(n));
}


Exemplo de código usando recursão em C

Crie um programa que calcule o fatorial de um número fornecido pelo usuário através da recursividade.
O fatorial de ‘n’ é representado por n!, onde:
n! = n * (n-1) * (n-2)*..1

O raciocínio desse exemplo é análogo ao do exemplo anterior, porém, vamos usar a multiplicação ao invés da soma.
Antes de resolvermos, vamos ver a idéia matemática por trás do fatorial.

Como dissemos na questão, para n=5:
5! = 5 * 4 * 3 * 2 * 1

Para n=4:
4! = 4 * 3 * 2 * 1

Para n=3:
3! = 3 * 2 * 1
E assim sucessivamente.
Porém, note que:
5! = 5 * 4 * 3 * 2 * 1 = 5 * 4!

E também:
4! = 4 * 3 * 2 * 1 = 4 * 3!

Podemos formular uma fórmula geral:
n! = n * (n-1)!

Abrindo esse produto, devemos parar somente quando o último elemento do produto for 1:
n! = n * (n-1)! = n * (n-1) * (n-2)! = n * (n-1) * (n-2) * ... * 1

Para programar isso, criamos uma função fatorial(int n) que retorna 1 se for passado 1 como argumento (pois fatorial(1) = 1) e caso o argumento seja maior que 1:
fatorial(n) = n * fatorial(n-1)

Isso, assim como no exemplo passado, e na maioria das funções usando a idéia de recursividade, é resolvido com um simples teste condicional IF ELSE.
Veja como ficou nosso código em C que calcula o fatorial:
#include <stdio.h>

int fatorial(int n)
{
    if(n == 1)
        return 1;
    else
        return ( n * fatorial(n-1) );
}

int main()
{
    int n;
    printf("Digite um inteiro positivo: ");
    scanf("%d", &n);

    printf("%d! = %d\n", n, fatorial(n));
}

Ou seja, pra calcular a função soma() é preciso usar a função soma().
Pra calcular o fatorial com a função fatorial() é preciso usar a função fatorial().
Entendeu agora o nome dessa lição?

40 comentários:

Anônimo disse...

Essa recursividade já tava me dando dor de cabeça. Esse site me clareou a idéia sobre o assunto.
Vlw

Apostila C Progressivo disse...

Olá amigo(a), que bom que te ajudou!

Quem estudar e não entender algo de algum tutorial, basta comentar que tentaremos explicar melhor.

Unknown disse...

Seu código está ok, só falta validar se o número é igual a zero pra não cair em loop infinito.

Apostila C Progressivo disse...

Olá Willian,

No primeiro exemplo vamos calcular a soma de "1+2+3+,,,+n" então estamos pressupondo que n é positivo, e ele nunca vai chegar a 0 (quando chega em 1, termina a recursão).

No exemplo 2, idem, visto que não existe fatorial de número negativo.

Concorda?

Unknown disse...

Vamos pensar que zero não é negativo nem positivo, no exemplo 1 se n>0 tudo bem porque ele vai para no if que valida se n=1, mas se a entrada para n for zero ai vai entrar em loop, isso se consider que 0 é não negativo.
No exemplo 2, na matemática 0!=1, na então acho necessário fazer esta validação.

Apostila C Progressivo disse...

Então, mas ao dizer que vamos somar de 1 até n e que n!=n*(n-1)*(n-2)*...*1 já estamos pressupondo que estamos esperando uma entrada que vai ser n>0. Ambos não são para caso de n<=0, embora possam ser alterados para isso.

Há várias maneiras de colocar o programa em loop infinito (colocando qualquer número negativo) ou mesmo dar um crash, colocando uma letra ou outro símbolo, ou um número fora do range dos inteiros, um float, etc etc, levando a inúmeros testes de validação para deixar a aplicação bem robusta, mas esse rigor não é o propósito do tutorial.

Unknown disse...

Ok, faz sentido.

Anônimo disse...

Esse post foi de grande valia para mim. Muito obrigado.

Anônimo disse...

Bacana de mais, clareza em seus comentarios.Valeu

Anônimo disse...

Porq não foi preciso um laço de repetição para verificar o fatorial?

Anônimo disse...

Willian Rojas está correto. Mesmo pedindo um inteiro positivo, você está deixando de lado o caso mais fundamental do fatorial, que é o zero. Se algum estudante olhar seu código, vai achar que não existe fatorial de zero. Não custa nada colocar um if(n==1 || n==0). Não vai deixar menos claro sua explicação e não vai atrapalhar nenhum estudante desavisado.

Anônimo disse...

Muito bom!! Poderiam colocar mais exemplos..

Anônimo disse...

mto legal :)

OsVaLdInHo... disse...

E como ele sabe quando parar?

Rafael Soares disse...

Gostei da maneira que você está ajudando ambos entenderem sobre essa função . Mais você nao tem tipo , uns videos aulas para link para gente ?
Porque a prof nao soube explicar direito esse assunto e semana que vem teremos Prova..
#Focotira10naprovak
Sou Academico: Ciência da Computação.

Unknown disse...

Excelente explicação.
Como eu poderia aplicar os cálculos recursivos de multiplicação em uma Estrutura de n Produtos, cada qual com sua composição de Insumos, que por sua vez também são compostos, até se chegar as Matérias-Primas?
Vocês tem alguma dica?

Grato
Haroldo

Anônimo disse...

Amigo, não sei ao certo mas o código que você citou não funciona, retorna sempre 1

#include

int fatorial(int n)
{
if(n == 1)
return 1;
else
return ( n * fatorial(n-1) );
}

int main()
{
int n;
printf("Digite um inteiro positivo: ");
scanf("%d", &n);

printf("%d! = %d\n", n, fatorial(n));
}
fabiano_jr1984@hotmail.com

Anônimo disse...

Essa recursividade só serve para isso ou tem outras aplicações??

Unknown disse...

O Código mais adequado seria esse,com certificação de não digitação de números menores que zero, e o fatorial de zero, que é 1.




int fatorial(int n)
{
if(n == 1 || n == 0)
return 1;
else
return(n * fatorial(n-1));
}

int main()
{
int n;

do
{
printf("Digite um inteiro positivo: ");
scanf("%d", &n);
} while(n<0);


printf("%d! = %d\n", n, fatorial(n));

return 0;
}

Anônimo disse...

Oi!
Primeiramente gostaria de agradecer; a sua gentileza e paciência de teres partilhado esse seu conhecimento connosco. eu sou estudante da faculdade ciências da universidade Agostinho Neto. podes não crer mais ela é uma das melhores de Angola(computação), mas o meu professor de imperativa não consegue transmitir esses conhecimentos computacionais, e o pessoal já notou nele muita falta de pedagogia. por isso suas dicas foram muito bem esclarecedoras: obrigado mais uma vez e um abraço de Angola.

Júlio Cardoso disse...

Parabéns pelo ótimo conteúdo. Ajudou bastante.

Unknown disse...

Não entendi o porquê do return 1, em meu programa, tanto o de soma como o de fatorial não funcionaram sem o return 1, mesmo o valor passado sendo diferente de 1.

Anônimo disse...

Parabéns pela explicação. Simples e efetiva! :)

Anônimo disse...

cara muito bom

Na rota: Mais um sonho ! disse...

Muito obrigada, foi devido a sua explicacão que consegui entender a questão da recursividade. Até então eu estava somente copiando o código.

Muito obrigada!! Você é fera!! Parabéns!

Na rota: Mais um sonho ! disse...

Muito obrigada, foi devido a sua explicacão que consegui entender a questão da recursividade. Até então eu estava somente copiando o código.

Muito obrigada!! Você é fera!! Parabéns!

Unknown disse...

Bom dia moçada.

Fiquei com a seguinte dúvida:

Digamos que no main eu utilize a formula do fatorial assim: Fatorial(4);

Entao no desvio da condição, vai para o else:

return n * fatorial(n-1);

Ai eu pergunto: em que momento o algoritmo multiplicou o 3 * 2 * 1?
Foi assim que me enrrolei :S

Unknown disse...

Bom dia:

Se no main, eu utilizar fatorial(4);
O algoritmo vai entender assim: return n * fatorial(n-1);

ou seja...

4 * fatorial(3);

Mas, em que momento do algoritmo ele multiplica 3 * 2 * 1 ?

Anônimo disse...

Olá! Parabéns me ajudaram muito a esclarecer a dúvida de como executar este tipo de programa.
Valeu.

Dalisson disse...

Voce consegue fazer uma função recursiva em c para logaritmo?

Erick disse...

Gostaria de saber o nome de quem escreveu esse artigo para usar como referência no meu trabalho

Roger disse...

Na verdade você pode incluir o 0 no fatorial, pois fatorial de 0 é 1. Então nesse caso, se o usuário entrar com 0, o resultado será 1.

Anônimo disse...

Excelente Texto, muito recomendado para tirar as dúvidas de quem está começando a programar em c euheuehue

Marcos Antonio disse...

Olá, alguém poderia me ajudar no seguinte problema?
Resolva a seguinte função recursiva escrita na linguagem C que devolve a soma de todos os elementos de um vetor, onde size é o tamanho do vetor. Assuma que os parâmetros passados ao registrador "sum" são: endereço do vetor no registrador $a0 e o valor size no registrador $a1. Os elementos do vetor são inteiros de 32 bits (words). Lembre-se de utilizar a pilha.

int sum( int vetor[], int size) {
if ( size ==0 )
return 0 ;
else
return sum ( vetor, size - 1 ) + vetor[ size - 1 ] ;
}

Betonine disse...

nt soma( int* vet, int n);



if (n==1)
{

return 1;

else
return (n+(n-1));

}

int main()
{
int n;
cout<<"Digite um inteiro positivo: ";
cin>>n;
cout<< "soma:"<< int soma (int* vet);
}

Unknown disse...

Olha, eu comecei a ver Recursividade a 8diaas atras e ja estava a aquecer !! Obgd pelo clareamento da materia

Élyda R.O disse...

Na verdade tem como você fazer da seguinte maneira existe fatorial de 0! =1 então ficaria assim :

If(n ==o)
return 1;
Else
return n*fatorial (n-1);

Ou seja , vai pegar partir de zero acho que assim e o limite do fatorial !!!

Alv3x disse...

achei deveras impressionante a forma como percebi este codigo, nao sei se é por ser bom em programacion ou porque é mesmo facil

Luis Gouveia de Santo António disse...

está muito porreiro

Felipe Mendes disse...

Que emoção finalmente entender a recursividade depois de dois dias quebrando a cabeça. Não tenho nem como agradecer pela ajuda!