[RESOLVIDO]Recursividade

Programação Java
#1

Estou estudando recursividade e java:

01 public class Fatorial {
02 public int Fatorialconta(int x) {  
03        if (x == 0) {
04         return 1;  
05        } else { 
06         return x * Fatorialconta(x -1);
07        }           
08    }  
09}

Perguntas:
a) Na linha “04” return 1, qual a razao de ser retornado o valor do calculo em vez de “1”. Eu troquei 1 para 2 o resultado fica
multiplicado por 2…troquei 1 para 3 o resultado fica multiplicado por 3…etc…etc…Pq isso acontece?

b) Alguem poderia explicar o funcionamento?? Nao consegui entender como eh acumulado o valor do resultado…Pq testei essa logica
e o resultado esta certo.!!

#2

Vamos lá… ja fez teste de mesa?

vamos supor que você envia o valor 5 pro seu método, o que ocorre então?

linha 3 : 5 é igual a 0? não, vamos para o else.
linha 6 : vamos retornar o valor de 5 multiplicado pelo retorno do Fatorialconta(4)

O método é iniciado novamente com um valor novo, 4.

Linha 3 : 4 é igual a 0? não, vamos para o else.
Linha 6 : vamos retornar o valor de 4 multiplicado pelo retorno do Fatorialconta(3)

O método é iniciado novamente com um valor novo, 3.

Linha 3 : 3 é igual a 0? não, vamos para o else.
Linha 6 : vamos retornar o valor de 3 multiplicado pelo retorno do Fatorialconta(2)

O método é iniciado novamente com um valor novo, 2.

Linha 3 : 2 é igual a 0? não, vamos para o else.
Linha 6 : vamos retornar o valor de 2 multiplicado pelo retorno do Fatorialconta(1)

O método é iniciado novamente com um valor novo, 1.

Linha 3 : 1 é igual a 0? não, vamos para o else.
Linha 6 : vamos retornar o valor de 1 multiplicado pelo retorno do Fatorialconta(0)

O método é iniciado novamente com um valor novo, 0.

Linha 3 : 0 é igual a 0? Sim!, retornamos 1. Agora temos um valor real para começar os cálculos!

agora caminhamos para trás.

Fatorialconta(0) = 1
Fatorialconta(1) = Fatorialconta(0) * 1 = 1 * 1 = 1
Fatorialconta(2) = Fatorialconta(1) * 2 = 1 * 2 = 2
Fatorialconta(3) = Fatorialconta(2) * 3 = 2 * 3 = 6
Fatorialconta(4) = Fatorialconta(3) * 4 = 6 * 4 = 24
Fatorialconta(5) = Fatorialconta(4) * 5 = 24 * 5= 120

agora o que acontece se o seu return fixo for de valor 2? Faça o teste.

É meio complicado mesmo no começo. Tem que ter bastante atenção. Como eu li uma vez: “Pra entender recursividade, antes precisa entender recursividade.” :wink:

EDIT: ah, quando for postar códigos use as tags [ code][/code]. Leia isso : Você é novo no GUJ? Vai criar um tópico e colar seu código-fonte? Leia aqui antes, por favor!

#3

A razão pela qual você retorna o valor 1 ao invés de um cálculo, é porque, por definição, o fatorial de 0 é 1.

Quando for escrever uma função recursiva você deve pensar:
a) Na regra recursiva;
b) Na condição de parada.

No caso, a condição de parada é atingir o menor fatorial possível, o de 0. Sabe-se que o fatorial de 0 é 1.

Os demais, podem ser obtidos pela função recursiva:

f(N) = N * f(N-1)
#4

Complementando. Acho que fica mais fácil se você entender primeiro o que é recursão e a definição de recursiva da função que você quer implementar.
Uma função recursiva é toda função que pode ser definida usando ela mesma.
No fatorial por exemplo:

0! = 1
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
…

Que é a mesma coisa que:
0! = 1
1! = 1 * 0!
2! = 2 * 1!
3! = 3 * 2!
4! = 4 * 3!
…

Perceba a substituição do pedaço da resolução pela a função. Ou seja, a função chama ela mesma!
Sendo assim, a definição recursiva da função fatorial pode ser dada por:

n! = 1, se n = 0
n! = n * (n-1)!, se n > 0

Note que na definição acima, o caso que faz a recursão parar é o primeiro, quando n for igual a 0. Sendo assim, n é a condição de parada, ou a base da recursão.
Se mudarmos n! para fatorial(n) da definição acima, veja o que teríamos:

fatorial(n) = 1, se n = 0
fatorial(n) = n * fatorial(n-1), se n > 0

Assim já fica mais parecido com a implementação não é mesmo?

Veja o arquivo em anexo de uma aula minha.

[]'s

#5

Opa !!! Boa Noite a todos…

Obrigado pela aula que todos me proporcionaram.

digaoneves, voce acabou de fritar os restos dos meus neuronios.
Quando coloquei return 2, o resultado ficou multiplicado por 2…

Uma duvida tecnica…O comando return 1 ele vai encerrar o metodo.ok?? Pq entao ele
retorna o calculo do fatorial e nao 1??

Andre

#6

Recursividade é um conceito que muitas pessoas têm dificuldade em entender como funciona.

Quando fazes Fatorialconta(5), o que é retornado é 5 * FactorialConta(4). Então é preciso is calcular o FactorialConta(4), que vai dar 4FactorialConta(3). Por sua vez FactorialConta(3) é 3FactorialConta(2). Continuando, FactorialConta(2) é 2* FactorialConta(1). E FactorialConta(1) é 1FactorialConta(0). Então aqui vamos entrar no if e vai devolver 1. Agora é andar para trás… Como já sabemos que FactorialConta(0) é 1, sabemos que Factorialconta(1) é 11, que é 1. Ja podemos calcular FactorialConta(2) que é 2*1, ou seja 2. E assim sucessivamente…

#7

Ola…

Este andar para tras…que nao consegui entender…Para mim se for igual a 0 ele vai retornar 1 e sairia do metodo…Mas isso nao acontece…

#8

[quote=acolen]Ola…

Este andar para tras…que nao consegui entender…Para mim se for igual a 0 ele vai retornar 1 e sairia do metodo…Mas isso nao acontece…

[/quote]

Sim, se for igual a 0 a função vai retornar 1, mas para quem ela vai retornar 1? Vai retornar para quem a chamou, e quem a chamou? Fatorial(1), logo Fatorial(1) vai retornar 11=1, mas para quem? Para quem a chamou!
Quem a chamou? Fatorial(2). Então Fatorial(2) vai retornar 21=2, para quem a chamou. Quem a chamou? Fatorial(3) , logo fatorial de 3 vai retornar 32=6 para quem a chamou. Quem a chamou, Fatorial(4), logo Fatorial(4) vai retornar 46=24 para quem a chamou. Quem a chamou? Fatorial(5), logo Fatorial(5) vai retornar 5*24=120 para quem a chamou. Quem a chamou? Você! Só então você recebe o resultado 120. Você não está entendendo porque não percebe que a função está sendo chamada por ela mesma várias vezes.

#9

cfred , Boa Noite !!!

Puts…Agora a ficha caiu…

Eu estava me enrolando todo era nessa logica final do metodo…Como ele proprio se chamou o return 1 retorna para ele mesmo…como fui eu que chamei
com valor 5 ele retorna para mim…Ou…valeu mesmo…agora entendi a logica disso…Brigadao…

Para mim pode fechar o topico…Agradeco realmente a todos…passei dias tentando entender isso…e nao conseguia…
OPs…e matei mais uma…Pq qdo coloco 2 no “return 1” altera o resultado…Valeu a todos…

Qual o procedimento para fechar um topico?

#10

Edite o seu primeiro post do tópico e adicione a tag [RESOLVIDO] no título :slight_smile: só isso.

#11