Aprendendo recursividade

77 respostas
R

Bom pessoal, estou tentando criar um código pra aprender recursividade ao gerar a série Fibonacci:
0 1 1 2 3 5 8 13...
Mas está dando um problema de "missing return statement" na linha 14. Não consegui entender pq.

class Fibonacci {
	int a=0;
	int b=1;
	int i;
	int calcula(int num){
	if (num <= 6){
		System.out.print(this.a + " , ");	
		System.out.print(this.b + " , ");
		this.a = this.a + this.b;
		this.b = this.b + this.a;
		this.i = this.i + 1;
		return calcula(num - 1);
	} else { System.out.println("Fim");}
	}
}
abaixo o main
class GeraSerie {
	public static void main(String[] args){
		
		Fibonacci fibo = new Fibonacci();
		
		int i = fibo.calcula(6);
		System.out.print(i);	
	}
}

agradecido desde já

77 Respostas

fernandosavio

Olá rafaelczy!
O erro está acontecendo porque sempre que um método declara que vai retornar algum valor ele é obrigado a retornar algo em todas as possibilidades de fluxo do algoritmo…
Resumindo a ópera: Se a condição do if for verdadeira o método retorna calcula(num-1)… Mas e se for falsa??? Seu código não retorna nada, e é isso que está impedindo seu código de ser compilado.
Espero ter ajudado!

R

fernandosavio:
Olá rafaelczy!
O erro está acontecendo porque sempre que um método declara que vai retornar algum valor ele é obrigado a retornar algo em todas as possibilidades de fluxo do algoritmo…
Resumindo a ópera: Se a condição do if for verdadeira o método retorna calcula(num-1)… Mas e se for falsa??? Seu código não retorna nada, e é isso que está impedindo seu código de ser compilado.
Espero ter ajudado!

Oi Fernando!
thanks men!
Essa teoria eu entendi mas nao exatamente como representar o tal retorno que falta no código não.
Sempre que num <= 6 vai chamar calcula(num) e quando nao for mais eu pus um “ELSE” seguido de um System.out.print(“Fim”); Eu achei que esse seria um retorno adequado.
Pode me ajudar dando um exemplo do retorno que eu deveria colocar escrito no codigo?
valeu

lordtiago

retorna um 0 aí =)

henriqueluz

Bom dia,

Cara, o retorno do seu método é um int, e no else você apenas escreve "Fim!" no console.
E isto não é considerado um retorno de método. Esse retorno é void.

Da uma analisada direitinho. Lembrando que o algoritmo de fibonacci é:

fibonacci(i) =
0, se i = 0
1, se i = 1
fibonacci(i-1) + fibonacci(i-2), se i >=2

É só transformar num método.
Abs,

R

Consegui galera:

class Fibonacci {
	int a=0;
	int b=1;
	int calcula(int num){
		int x = num;
		if (x <= num && x >= 1){
			System.out.print(this.a + " , ");	
			System.out.print(this.b + " , ");
			this.a = this.a + this.b;
			this.b = this.b + this.a;
			return calcula(x-1);
		}
 		else {
			System.out.println(" ");
			System.out.println("Fim");
			return 0;
		}
	}
}

Bom agora cumpri o que pede: gerar a serie usando recursividade. o exercício tb pede pra depois gerar a serie mas usando só uma linha de codigo (usando operador ternario)
Alguem pode postar um código de exemplo pro problema em questao ai galera?
Outra coisa: Tem um jeito de eu dar o retorno pedido no metodo calcula(num) sem imprimir zero como ta sendo o caso ai em cima?
valeu

henriqueluz

Para entender o operador ternário, vou te dar um exemplo que faz a mesma coisa com o if.

if(i&lt;=0){
    fatorial = 0;
}else{
    fatorial = i*fatorial(i-1);
}
return fatorial;

//Operador ternário
fatorial = (i &lt;= 0) ? 0 : i*fatorial(i-1);

Basta adaptar.

Abs,

R

henriqueluz:
Para entender o operador ternário, vou te dar um exemplo que faz a mesma coisa com o if.

if(i&lt;=0){
    fatorial = 0;
}else{
    fatorial = i*fatorial(i-1);
}
return fatorial;

//Operador ternário
fatorial = (i &lt;= 0) ? 0 : i*fatorial(i-1);

Basta adaptar.

Abs,

fatorial = (i &lt;= 0) ? 0 : i*fatorial(i-1); // Não entendi o "(i &lt;= 0)" , o "?" e o ":" - como se lê essa linha de código?

valeu

R

opss… a primeira expressao entre aspas que eu citei informei erradamente que nao entendi - mas só nao entendi mesmo o “?” e o “:”

henriqueluz

Cara o “?” é o operador ternário.
E o que vem após ele é o que deve ser retornado e atribuido.
(condição) ? SE CONDIÇÃO FOR VERDADE RETORNA AQUI : SE FOR FALSA RETORNA AQUI

entendeu?

R

henriqueluz:
Cara o “?” é o operador ternário.
E o que vem após ele é o que deve ser retornado e atribuido.
(condição) ? SE CONDIÇÃO FOR VERDADE RETORNA AQUI : SE FOR FALSA RETORNA AQUI

entendeu?

Sim cara, com esso ultimo exemplo entendi. legal tua leitura, simples de entender.
Agora vou tentar adptar com o operador ternário pra ver se consigo gerar a serie fibonacci numa linha só.
thank’s men!
i talk in english but my love is Brasil

R

Bom, to tentado agora gerar a serie Fibonacci com o operador ternário mas ta dando erro de “unexpected type” bem em cima do “?” que no caso é o operador ternário, ou seja, nao escrevi direito a expressão e ele nao ta reconhcendo.

class Fibonacci {
	int calcula(int a, int b){
		(a==0 && b==1) ? a , b : a=a+b && b=b+a; calcula(a,b);	
	}
}
class GeraSerie {
	public static void main(String[] args){
		
		Fibonacci fibo = new Fibonacci();
		
		int i = fibo.calcula(0, 1);
		System.out.print(i);	
	}
}

O que eu queria executar na linha do op. ternario seria: pra ele retornar 0 e 1 (na primeira chamada )e nas chamadas posteriores(recursivas) da função imprimir A valendo A+B e B valendo B+A

ta por ai ainda henrique?

ruben_m

Eix a funçaão Recursiva para calculo da serie de fibonacci

public static int fib(int i){ if (i==1 ||i==2) return 1; else return (fib(i-1)+fib(i-2)); }

fernandosavio

Cara…
O operador ternário não pode ser usado a qualquer momento…
Eis a explicação:
(Condição) ? O QUE RETORNARÁ SE TRUE : O QUE RETORNARÁ SE FALSE ;

Se você fizer isso:

(a>b)?"a é maior que b" : "a é menor ou igual a b";

Você jogará fora o retorno do condicional ternário.
Se você atribuir esse retorno a alguma variável o compilador permitirá que o código compile:

String retorno = (a>b)?"a é maior que b" : "a é menor ou igual a b";
//Ou ainda
return (a>b)?"a é maior que b" : "a é menor ou igual a b";

Entendeu?

R
fernandosavio:
Cara... O operador ternário não pode ser usado a qualquer momento... Eis a explicação: (Condição) ? O QUE RETORNARÁ SE TRUE : O QUE RETORNARÁ SE FALSE ; Se você fizer isso:
(a>b)?"a é maior que b" : "a é menor ou igual a b";
Você jogará fora o retorno do condicional ternário. Se você atribuir esse retorno a alguma variável o compilador permitirá que o código compile:
String retorno = (a>b)?"a é maior que b" : "a é menor ou igual a b";
//Ou ainda
return (a>b)?"a é maior que b" : "a é menor ou igual a b";

Entendeu?

Sim
Mas olha só meu código abaixo, eu tenho duas variaveis A e B dentro da condição e quero que retorne um valor para cada variável a depender se A==0 e B==1.
Com o Return q vc sugeriu dá "unexpected type" no op ternario. E armazenar A e B numa variavel? É possível? E depois complicou mais ainda pq quero que tanto na opção FALSE do op ternario qto na opção TRUE dele execute mais de uma orientação e to perdidão na sintaxe

Fibonacci {
	int calcula(int a, int b){
		return (a==0 && b==1) ? a , b  a=a+b && b=b+a calcula(a,b): a=a+b && b=b+a; calcula(a,b); /* como A e B começam com 0 e 1 então retorna e imprime 0 e 1 (os dois primeiros numeros da serie fibonacci). Não to conseguindo isso e além disso ainda teria outra orientação que após retornar 0 e 1 faria a operação de soma das variaveis A e B, dai chamaria de novo a função. Dai A valendo 1 e B valeno 2 ao entrar na interrogação da condição (a==0 && b==1) novamente darial FALSO e em todas chamadas posteriores tb, e a partir de entao sempre somando e atualizando A e B e imprimindo as duas e rechamando a função. Fiz uma salada ai no codigo pra poder me fazer entender */ 	
	}
abaixo o main
class GeraSerie {
	public static void main(String[] args){
		
		Fibonacci fibo = new Fibonacci();
		
		int i = fibo.calcula(0, 1);
		System.out.print(i);	
	}
}

valeu

fernandosavio

Teu código está meio confuso…
Mas vamos lá.
Não é possível retornar duas variáveis, nem com operador ternário nem com nada. Porém é possível retornar um array com dois valores!

Não sei se seus conceitos de recursão estão bem estudados, mas vou mandar um exemplo que fiz agora de Fibonacci com recursão para você ver.

public static void main(String args[]) {
		int elem1 = 0;	//Primeiro elemento Fibonacci
		int elem2 = 1;	//Segundo elemento Fibonacci

		//Chama o método recursivo
		calculaFibonacci(elem1,elem2);
	}

	static int calculaFibonacci(int a, int b){

		if(b>500){		//O número 500 é o critério de parada da recursão
			return 0;	//Aqui simplesmente encerra com a recursão, não nenhum efeito relevante nos cálculos
		}else{
			System.out.println(a);	//Imprime no console o elemento atual
			return calculaFibonacci(b, a+b);	//Chama recursivamente o cálculo dos próximos elementos
		}
	}
ruben_m

Voces estão a aplicar recursividade nessas Soluções?

fernandosavio

sim ruben_m…
Estamos tentando ajudar o companheiro a aprender recursividade usando como exemplo Fibonacci…

R

Engraçado
Na apostila da caelum no fim do cap 4 - seção 4.13 pede pra resolver a serie fibonacci com recursividade e op. ternario em apenas uma linha.
Se eles pedem isso é pq é possível mas como se eu não posso ter duas variaveis dentro da condição e muito menos dar mais de uma instrução no caso FALSE e no caso TRUE

class Fibonacci {
	int calcula(int a, int b){
                return (se A vale 0 e B vale 1) ? IMPRIME a , b apos isso INCREMENTA a . b e CHAMA calcula(a,b) de novo : SE NAO ENTAO IMPRIME  a=a+b && b=b+a e CHAMA calcula(a,b) de novo; // se isso fosse possível resolveria o problema mas se nao é então como resolver com recursividade e operador ternário numa linha , se tem duas variaveis na condição e mais de duas intruções em cada uma das condições TRUE  e FALSE ?
	}
}

Eu vi teu exemplo Fernandosavio resolvendo com IF e recursividade mas esse eu assimilei.

alguma ideia ai ?

R

rafaelczy:
Engraçado
Na apostila da caelum no fim do cap 4 - seção 4.13 pede pra resolver a serie fibonacci com recursividade e op. ternario em apenas uma linha.
Se eles pedem isso é pq é possível mas como se eu não posso ter duas variaveis dentro da condição e muito menos dar mais de uma instrução no caso FALSE e no caso TRUE

class Fibonacci {
	int calcula(int a, int b){
                return (se A vale 0 e B vale 1) ? IMPRIME a , b apos isso INCREMENTA a . b e CHAMA calcula(a,b) de novo : SE NAO ENTAO IMPRIME  a=a+b && b=b+a e CHAMA calcula(a,b) de novo; // se isso fosse possível resolveria o problema mas se nao é então como resolver com recursividade e operador ternário numa linha , se tem duas variaveis na condição e mais de duas intruções em cada uma das condições TRUE  e FALSE ?
	}
}

Eu vi teu exemplo Fernandosavio resolvendo com IF e recursividade mas esse eu assimilei.

alguma ideia ai ?

Sim welintom o seu exemplo e a teoria/sitaxe do op. ternario eu tb entendi. Mas o lance mesmo é como vc pode ver ai em cima eu fiz uma salada (literalmente) no código pra ilustrar: Temos duas variaveis dentro da condição pra retornar e ainda dentro do FALSE e dentro do TRUE tem mais de uma orientação como vc pode ver.
Fiz assim pq o exercicio pede pra resolver a serie fibonacci em 1 linha apenas com recursividade e op ternario.

Tem algum jeito na sua opinião de resolver como é pedido o exercicio ?
valeu

R

wellington.nogueira:
Cara,

Tenho a linha resolvida aqui. Só não postei pq o interesse é que você aprenda. Se teoricamente, você entendeu, não deve ser difícil resolver.
Como disse, montei a estrutura, é só trocar os bloquinhos. Teu único “problema” é onde vai ficar o Sysout. MAs isso te ajudo a resolver depois que você montar a linha do ternário.

if(b>500){ //CONDICAO return 0; //RESULTADO_CASO_CONDICAO_VERDADEIRO }else{ System.out.println(a); //tire isso daqui. return calculaFibonacci(b, a+b); //RESULTADO_CASO_CONDICAO_FALSO } //Coloque o return antes do ternário (não pode haver o return entre os sinais [b]?:;[/b])

Ternário é um pouco estranho mesmo, mas uma vez compreendido, fica muito simples ;)

Brother o ternário que eu quero montar é assim:

return (b>500) ? 0 : System.out.println(a) E CHAMA calculaFibonacci(b, a+b);
escrevi misturando codigo com figuração mas é isso: na condição VERDADEIRO quero que ele execute IMPRIME A e ainda CHAME calculaFibonacci(b, a+b); (duas orientações pra condição FALSO !! pode ?)
Outra coisa: E se dentro da condição eu quisesse nao só testar o B mas o A tb, poderia ?
valeu

R

wellington.nogueira:
Ternário é uma forma de atribuir um valor ou outro conforme uma determinada regra.

Ou seja, é para um uso muito específico.
Exemplo: int variavel = 0; if(condicao) { variavel = 1; } else { variavel = 2; }
Neste exemplo, variavel é inicializada com zero. De acordo com uma condição específica, se a mesma for verdadeira, é atribuido 1; se for falsa, é atribuído 2.
Neste contexto, podemos alterar para um ternário ( o operador ternário é representado por ?: )
Exemplo convertido:

int variavel = 0; variavel = condicao ? 1 : 2; ou int variavel = condicao ? 1 : 2; //A inicialização foi suprimida, neste exemplo é desnecessário.

O valor que fica entre ? e : deve ser do mesmo tipo que o que fica entre : e ;.

Não é permitida mais que uma instrução em cada parte do ternário, ou seja, o exemplo abaixo não é permitido.

int variavel = condicao ? System.out.println("Valor"); 1 : 2;


Pois é, aqui tu responde para da minha questao: “Não é permitida mais que uma instrução em cada parte do ternário”
Entao como proceder pra gerar a serie fibonacci recursivamente e usando o op ternario em apenas uma linha …humm…bom desafio…

fernandosavio

Cara, o Wellington mastigou tudo pra você, não precisa nem pensar em nada é só pegar o código acima completar as lacunas no código abaixo:

return CONDICAO ? RESULTADO_CASO_CONDICAO_VERDADEIRO : RESULTADO_CASO_CONDICAO_FALSO ;

E eu tenho a apostila da Caelum também… É sim, um desafio, mas se você quer fazer em uma linha você não conseguirá imprimir!
E é um desafio estranho, porque qualquer programador que veja um código desses em uma linha já chutaria a canela de quem fez isso! Dar manutenção em código bruxo é fogo!

R

wellington.nogueira:
fernandosavio:
Cara, o Wellington mastigou tudo pra você, não precisa nem pensar em nada é só pegar o código acima completar as lacunas no código abaixo:

return CONDICAO ? RESULTADO_CASO_CONDICAO_VERDADEIRO : RESULTADO_CASO_CONDICAO_FALSO ;

E eu tenho a apostila da Caelum também… É sim, um desafio, mas se você quer fazer em uma linha você não conseguirá imprimir!
E é um desafio estranho, porque qualquer programador que veja um código desses em uma linha já chutaria a canela de quem fez isso! Dar manutenção em código bruxo é fogo!

Consegue imprimir sim :wink:
Existem malícias no ternário que só Beelzebuth pra agradecer :twisted:
Essa desse exercício é simples. Fica, inclusive, elegante hehe.

Só pra exemplificar HellCode, veja esse: I Love Ternary

Cosengue imprimir sim? puxa cara nem sem imprimir eu consegui montar isso tudo com o op ternario em apenas uma linha e gerar a serie fibonacci. Podes mostrar ai?
thank’s

R

fernandosavio:
wellington.nogueira:

if(b>500){ //CONDICAO return 0; //RESULTADO_CASO_CONDICAO_VERDADEIRO }else{ System.out.println(a); //tire isso daqui. return calculaFibonacci(b, a+b); //RESULTADO_CASO_CONDICAO_FALSO } //Coloque o return antes do ternário (não pode haver o return entre os sinais [b]?:;[/b])

Cara, o Wellington mastigou tudo pra você, não precisa nem pensar em nada é só pegar o código acima completar as lacunas no código abaixo:

return CONDICAO ? RESULTADO_CASO_CONDICAO_VERDADEIRO : RESULTADO_CASO_CONDICAO_FALSO ;

E eu tenho a apostila da Caelum também… É sim, um desafio, mas se você quer fazer em uma linha você não conseguirá imprimir!
E é um desafio estranho, porque qualquer programador que veja um código desses em uma linha já chutaria a canela de quem fez isso! Dar manutenção em código bruxo é fogo!


eu penso que terei de ser algo mais ou menos assim:

class Fibonacci {
	int calcula(int a, int b){
		return (b>500) ? 0 : System.out.println(a) DAI CHAMA calcula(b, a+b);	
	}
}

mas foi me dito que nao pode duas instrições nem no TRUE nem no FALSE.

fernandosavio

Assim dá pra fazer uma classe toda em uma linha!
eauheuhaheuuahe

R
wellington.nogueira:
Cara,

Tenho a linha resolvida aqui. Só não postei pq o interesse é que você aprenda. Se teoricamente, você entendeu, não deve ser difícil resolver.
Como disse, montei a estrutura, é só trocar os bloquinhos. Teu único "problema" é onde vai ficar o Sysout. MAs isso te ajudo a resolver depois que você montar a linha do ternário.

if(b>500){       //CONDICAO
            return 0;   //RESULTADO_CASO_CONDICAO_VERDADEIRO    
        }else{    
            System.out.println(a);  //tire isso daqui.
            return calculaFibonacci(b, a+b);    //RESULTADO_CASO_CONDICAO_FALSO  
        }
        //Coloque o return antes do ternário (não pode haver o return entre os sinais [b]?:;[/b])

Ternário é um pouco estranho mesmo, mas uma vez compreendido, fica muito simples ;)

ok Brother! Peguei a tua logica (pq a minha nao funfa com ternario devido a ter mais de uma instrução) e montei o ternario, mas eu confesso que com a tua lógica ficou muito facil construir o ternario. Tenho a impressão q eu tava quebrando a cabeça em cima do ternario mas o problema é que nunca ia dar mesmo pq eu tinha que mudar pra uma lojica mais sucinta pra poder ser aceita na sintaxe do ternario.
class Fibonacci {
	int calcula(int a, int b){
		return (b > 500) ? 0 : calcula(b, a+b);	
	}
}

[code]class GeraSerie {
	public static void main(String[] args){
		
		Fibonacci fibo = new Fibonacci();
		
		int i = fibo.calcula(0, 1);
		System.out.print(i);	
	}
}

tinha que te me esforçado mais pra sair da minha lógica (duas instruções pra procesar):
a = a + b
b = b + a
e descobrir a tua(uma instrução apenas):
(b, b + b)

Assim compilou e rodou ok (claro: Permanece o problema de "como vai imprimir" sem ferir o que o exercicio pede que é "recursividade+ternario+1 linha só")

to até fazendo teste de mesa aqui pra entender essa logica passo a passo pq nao saquei legal ainda.

R

Na verdade Welingtom eu nao achei ternario estranho mas o que complicou mesmo é que eu queria algo impossivel: dar mais de uma instrução pra FALSE e mais de uma pra TRUE
abração

R

puxa vida!!!
agora que descobri que a logica q eu usava funfa com ternario se eu botar ela dentro do parenteses da re-chamada da função calcula()

class Fibonacci {
	int calcula(int a, int b){
		return (b > 500) ? 0 : calcula(a=a+b, b=b+a);	
	}
}

4 dias pra sacar isso …ufsssss… eta curva de aprendizam longa essa do java (tinha que ser JAVEX tao rapido de aprender qto enviar carta pelo SEDEX)
rssss
mas valeu , instigou pra caramba e dai fixei hehhe

R

wellington.nogueira:
rafaelczy:

eu penso que terei de ser algo mais ou menos assim:

class Fibonacci {
	int calcula(int a, int b){
		return (b>500) ? 0 : System.out.println(a) DAI CHAMA calcula(b, a+b);	
	}
}

mas foi me dito que nao pode duas instrições nem no TRUE nem no FALSE.


Sim, não pode mesmo. A idéia é quase essa. Tire o System.out.println(a) colocando-o na linha de cima primeiro.

int calcula(int a, int b){ System.out.println(a); return (b>500) ? 0 : calcula(b, a+b); }

Se quiser uma linha, alinhe os comandos e pronto, está tudo numa linha.

System.out.println(a); return (b>500) ? 0 : calcula(b, a+b);

Baita pega ratao da apostila - me cravei todo pq achava q o exercicio queria tudo numa linha sem essa de “;” pra disfarçar. Como foi dito “Assim da pra construir uma classe inteira e uma linha”

R

detalhe, essa logica nao gera a serie

int calcula(int a, int b){ System.out.println(a); return (b>500) ? 0 : calcula(b, a+b); }

essa gera ok:

class Fibonacci { int calcula(int a, int b){ System.out.print(a + "" + b); return (b > 500) ? 0 : calcula(a=a+b, b=b+a); } }

mas tua ajuda foi fundamental men!

R

opssss…(conforme manda o exercicio)

class Fibonacci {
	int calcula(int a, int b){
		System.out.print(a + "" + b);return (b > 500) ? 0 : calcula(a=a+b, b=b+a);	
	}
}
ruben_m
public class fibonacci{

public static int fib(int i){
    if (i==1 ||i==2)
        return 1;
    else
        return (fib(i-1)+fib(i-2));
}
public static void main (String[] args){
fibonacci f = new fibonacci();
int n = Integer.parseInt((JOptionPane.showInputDialog("Introduza a quantidade de elementos a serem imprimidos"));

for(int i = 0;i<n;i++){
System.out.println(f.fib(i));
}
fernandosavio

wellington.nogueira:
fernandosavio:
Assim dá pra fazer uma classe toda em uma linha!
eauheuhaheuuahe

É que, na minha opinião, a impressão do resultado não está inclusa nessa história de colocar numa linha só ;)

Concordo plenamente!
Foi o que pensei desde o início. Pois imprimir o resultado não faz parte da Sequencia de Fibonacci!
O que eu pensei foi isso:

public class MainTeste {

	public static void main(String args[]){
		System.out.println(fibonacci(8, 0, 1));

	}
	public static int fibonacci(int limite, int a, int b){                 //Limite=enésimo elemento da sequência
		return (limite>1) ? fibonacci(limite-1, b, a+b) : a ;
	}
}

Aí retorna só o número que realmente se precisa saber

R

Bom galera, jamais pensei q iria encher 3 paginas de posts pra gerar esse fibonacci de todas formas pedidas (num de var livre, depois 2 var apenas, depois recursividade, depois ternario + recursividade + 1 linha só) ufsss… 7 dias morando no forum…
mas valeu
fixei legal recursividade e op ternario
parabens ai pros atores principais da comedia q ajudaram e determinaram o sucesso
Welligton nogueira e Fernando savio
a todos demais thank’s to!

After thousands of years in caelum apostila charpeter 4 finaly going to the charpter 5 :shock:

fernandosavio

Eu já conhecia recursividade e operadores ternário mas também foi um aprendizado…
Não precisa agradecer, qualquer coisa mais que precisar e eu souber estamo aí!

R

Mais uma questão galera:
A apostila da caelum fala no fim do cap.4 qdo pede pra gerar a serie fibonacci usando recursividade, que essa tecnica é mais demorada em materia de processamento que um laço comum.
Por que pessoal ?
achei interessante a questão!

fernandosavio

A recursividade é mais custosa em termos de processamento. Pois o Sistema Operacional aloca espaço para uma função Fibonacci e ela chama ela mesmo, então essa primeira instância fica na memória e o sistema operacional empilha outra instância do método na memória, e aí ele chama ele de novo e cria outra instância… e por aí vai! A última instância retornará a resposta requisitada e retornará para a instância que a chamou até chegar na primeira instância do método que retornará para o usuário a resposta desejada…
Resumo: O SO empilha os métodos recursivos até que algum deles retorne e desempilha tudo.
Então a recursividade gasta mais porque cria várias instâncias do mesmo método até que ele se resolva.

Espero não ter complicado muito!

R

fernandosavio:
A recursividade é mais custosa em termos de processamento. Pois o Sistema Operacional aloca espaço para uma função Fibonacci e ela chama ela mesmo, então essa primeira instância fica na memória e o sistema operacional empilha outra instância do método na memória, e aí ele chama ele de novo e cria outra instância… e por aí vai! A última instância retornará a resposta requisitada e retornará para a instância que a chamou até chegar na primeira instância do método que retornará para o usuário a resposta desejada…
Resumo: O SO empilha os métodos recursivos até que algum deles retorne e desempilha tudo.
Então a recursividade gasta mais porque cria várias instâncias do mesmo método até que ele se resolva.

Espero não ter complicado muito!

Logo, se eu desejo criar uma aplicação leve e rápida pra uma plataforma com pouca mem RAM e pouca vel de processador, o negócio é evitar recursividade. certo?

sowyer

rafaelczy:
fernandosavio:
A recursividade é mais custosa em termos de processamento. Pois o Sistema Operacional aloca espaço para uma função Fibonacci e ela chama ela mesmo, então essa primeira instância fica na memória e o sistema operacional empilha outra instância do método na memória, e aí ele chama ele de novo e cria outra instância… e por aí vai! A última instância retornará a resposta requisitada e retornará para a instância que a chamou até chegar na primeira instância do método que retornará para o usuário a resposta desejada…
Resumo: O SO empilha os métodos recursivos até que algum deles retorne e desempilha tudo.
Então a recursividade gasta mais porque cria várias instâncias do mesmo método até que ele se resolva.

Espero não ter complicado muito!

Logo, se eu desejo criar uma aplicação leve e rápida pra uma plataforma com pouca mem RAM e pouca vel de processador, o negócio é evitar recursividade. certo?

Exato ! :thumbup:

R

sowyer:
rafaelczy:
fernandosavio:
A recursividade é mais custosa em termos de processamento. Pois o Sistema Operacional aloca espaço para uma função Fibonacci e ela chama ela mesmo, então essa primeira instância fica na memória e o sistema operacional empilha outra instância do método na memória, e aí ele chama ele de novo e cria outra instância… e por aí vai! A última instância retornará a resposta requisitada e retornará para a instância que a chamou até chegar na primeira instância do método que retornará para o usuário a resposta desejada…
Resumo: O SO empilha os métodos recursivos até que algum deles retorne e desempilha tudo.
Então a recursividade gasta mais porque cria várias instâncias do mesmo método até que ele se resolva.

Espero não ter complicado muito!

Logo, se eu desejo criar uma aplicação leve e rápida pra uma plataforma com pouca mem RAM e pouca vel de processador, o negócio é evitar recursividade. certo?

Exato ! :thumbup:


Então qdo q recursividade é uma escolha ideal de código, se ela gasta mais memoria e processador?

fernandosavio

Para percorrer árvores, por exemplo, é uma das poucas maneiras possíveis… (que eu conheço é a única)…

R

Pessoal ! agora to me matando pra gerar a serie fibonacci com array + recusividade!
Pensei q eu tava safo mas me fu… de novo hehehe!
bom olhem ai o meu main:

class fibonacciArrayRecursivo{
	public static void main(String[] args){
			gera teste = new gera();
			
			gera.calcula(2);	
	}
}

e aqui minha querida classezinha:

class gera{
		int[] fibonacci = new int[20];
		fibonacci[0] = 0;
		fibonacci[1] = 1;
		
		System.out.print(this.fibonacci[0]); // aqui ja matou os dois primeiros nums da serie		
		System.out.print(this.fibonacci[1]);

		int calcula(int i){ // aqui passa como parametro 2 que é a terceira casa do array
			while (i < 20){ // condição pra parar qdo chegar na ultima posição do vetor
				this.fibonacci[i] = this.fibonacci[i - 1] + this.fibonacci[i - 2]; // logica é posição 3 = posição 2 + posição 1
				i = i + 1; // incremento da posição
				return this.calcula[i]; // chama de novo o metodo mas dessa vez pede pra calcular o valor contido na prox posição
			}
		}

}

simplesmente tem 37 erros…urghh :shock:

R

galera tentei arrumar alguns erros e editei de novo aqui:

public static void main(String[] args){
			gera teste = new gera();
			
			gera.calcula(3);	
	}
}
class gera{
		int[] fibonacci = new int[20];
		fibonacci[0] = 0;
		fibonacci[1] = 1;
		
		System.out.print(this.fibonacci[0]);		
		System.out.print(this.fibonacci[1]);

		void calcula(int i){
			while (i < 20){
				this.fibonacci[i] = this.fibonacci[i - 1] + this.fibonacci[i - 2];
				i = i + 1;
				calcula();
			}
		}

}

nao acredito q eu esteja me matando com uma logica tao simples: posição n = posição n-1 + posição n-2 :shock:

sowyer

rapz!.. vc chama o calcula e não passa o parâmetro ?? pq ?

R

sowyer:
rapz!.. vc chama o calcula e não passa o parâmetro ?? pq ?


eu achei que nao precisava pois ao chamar calcula ele volta na linha 9 e encontra o parametro “i”. Quer dizer que na linha 13 tenho de passar o parametro “i” ?

fernandosavio
public class MainTeste {  
  
    public static void main(String args[]){  
        System.out.println(fibonacci(8, 0, 1));  
  
    }  
    public static int fibonacci(int limite, int a, int b){    //Limite=enésimo elemento da sequência  
        return (limite>1) ? fibonacci(limite-1, b, a+b) : a ;  
    }  
}
R
fernandosavio:
public class MainTeste {  
  
    public static void main(String args[]){  
        System.out.println(fibonacci(8, 0, 1));  
  
    }  
    public static int fibonacci(int limite, int a, int b){    //Limite=enésimo elemento da sequência  
        return (limite>1) ? fibonacci(limite-1, b, a+b) : a ;  
    }  
}
Fernando eu tenho q resolver esse usando array+recursividade. se puder ajeitar meu codigo fica mais facil pra mim entender pq a logica é minha valeu
fernandosavio

Repense seu código…
Não existe recursividade que tenha algum nexo que retorne void…
Ela tem que retornar algo para o método anterior na pilha poder trabalhar com ele…

R

fernandosavio:
Repense seu código…
Não existe recursividade que tenha algum nexo que retorne void…
Ela tem que retornar algo para o método anterior na pilha poder trabalhar com ele…

eu tb achei isso mas mudei o metodo pra void pq antes o metodo era int e eu nao conseguia compilar.
Ja tentei com int o metodo e ja nao sei mais o que fazer.
pode dar alguma pista?

fernandosavio
public class MainTeste {

	static int[] vet;

	public static void main(String args[]){
	   int nElementos = 10;	//Escolhe o tamanho do vetor
		vet = new int[nElementos];
	   vet[0] = 0;
	   vet[1] = 1;
	   calcula(2);
	   for(int n : vet){
	   	System.out.println(n);
	   }
	}

	public static void calcula(int nodoAtual){
		if(nodoAtual==vet.length){
			return;
		}else{
			vet[nodoAtual] = vet[nodoAtual-2] + vet[nodoAtual-1];
			calcula(nodoAtual+1);
		}
	}
}
fernandosavio

Assim dá para fazer com void…
É importante você saber que toda recursividade necessita de um critério de parada. No meu caso foi o fim do vetor.

Qualquer dúvida pergunte…

R
Fernando acho q to chegando la. eu estava cometendo o erro fazer operações de atribuição e comandos imprimir dentro da classe gera. Agora criei um metodo contrutor gera onde coloquei esses comandos e só ta dando 1 erro dos 37 que davam antes:
class gera{
		int[] fibonacci = new int[20];
		
		gera(){
			fibonacci[0] = 0;
			fibonacci[1] = 1;
			System.out.print(this.fibonacci[0]);		
			System.out.print(this.fibonacci[1]);
		}

		int calcula(int i){
			while (i < 20){
				this.fibonacci[i] = this.fibonacci[i - 1] + this.fibonacci[i - 2];
				i = i + 1;
				calcula(i);
			}
		}
}
o main
class fibonacciArrayRecursivo{
	public static void main(String[] args){
			gera teste = new gera();
			
			gera.calcula(2);	
	}
}

da um erro de "non=static method calcula(int) cannot be refered from a static context"
gera.calcula(2);
^nao entedi esse erro cara

R

coloquei o metodo calcula como void e nao mais int e agora ta compilando ok

fernandosavio

Se um método é static se chama o método assim:

NomeDaClasse.metodoEstatico();

Se um método não é static, ou seja, precisa ser chamada apartir de um objeto, se chama o método assim:

NomeDaClasse novoObjeto = new NomeDaClasse();
novoObjeto.metodoNaoEstatico();

Fui claro?

R

no main eu ta invocando o metodo assim:
gera.calcula(2);

e o certo é:
teste.calcula(2);

que tanso!
agora compila ok

Era isso q vc queira dizer Fernando?

R
class fibonacciArrayRecursivo{   
    public static void main(String[] args){   
            gera teste = new gera();   
               
            teste.calcula(2);       
    }   
}
R

porem me falaram que:
compila mas-

class gera{
		int[] fibonacci = new int[20];
		
		gera(){
			fibonacci[0] = 0;
			fibonacci[1] = 1;
			System.out.print(this.fibonacci[0]); //foi dito que aqui nao executa nada		
			System.out.print(this.fibonacci[1]); // e nem aqui !!! onde ponho isso entao? E pq isso é assim?
		}

		void calcula(int i){
			while (i < 20){
				this.fibonacci[i] = this.fibonacci[i - 1] + this.fibonacci[i - 2];
				i = i + 1;
				calcula(i);
			}
		}
}
fernandosavio

Exatamente!
Por isso é muito importante entender os conceitos de OO!

R
rafaelczy:
porem me falaram que: compila mas-
class gera{
		int[] fibonacci = new int[20];
		
		gera(){
			fibonacci[0] = 0;
			fibonacci[1] = 1;
			System.out.print(this.fibonacci[0]); //foi dito que aqui nao executa nada		
			System.out.print(this.fibonacci[1]); // e nem aqui !!! onde ponho isso entao? E pq isso é assim?
		}

		void calcula(int i){
			while (i < 20){
				this.fibonacci[i] = this.fibonacci[i - 1] + this.fibonacci[i - 2];
				i = i + 1;
				calcula(i);
			}
		}
}
me disseram q meus comandos print nao executam dentro metodo construtor gera(){} - Pq e como devo fazer ? Fernando, o que sao conceitos OO ?
R

bah q tanso rsss sou eu OO = orientação a objetos
Se alguem pudem me ajudar no post antes deste eu agradeço (comandos dentro do metodo contrutor gera() nao funfam)

fernandosavio

Os comandos executam sim dentro do contrutor…

public class Gera{

	int[] fibonacci = new int[20];

	Gera(){
		fibonacci[0] = 0;
		fibonacci[1] = 1;
		System.out.print(this.fibonacci[0] + " - ");
		System.out.print(this.fibonacci[1] + " - ");
	}

	void calcula(int i){
		if (i < 20){
			this.fibonacci[i] = this.fibonacci[i - 1] + this.fibonacci[i - 2];
			System.out.print(fibonacci[i] + " - ");
			i = i + 1;
			calcula(i);
		}else
			return;
	}
}

e a main:

public class MainTeste {

	public static void main(String args[]){
		Gera x = new Gera();
		x.calcula(2);
	}
}
R

fernandosavio:
Os comandos executam sim dentro do contrutor…

public class Gera{                                                                       // aqui tu botaste "public" antes do gera - pode me explicar?

	int[] fibonacci = new int[20];

	Gera(){
		fibonacci[0] = 0;
		fibonacci[1] = 1;
		System.out.print(this.fibonacci[0] + " - ");
		System.out.print(this.fibonacci[1] + " - ");
	}

	void calcula(int i){
		if (i < 20){                                                 // aqui tu substuíste o me 'while' por IF . Pq?
			this.fibonacci[i] = this.fibonacci[i - 1] + this.fibonacci[i - 2];
			System.out.print(fibonacci[i] + " - ");
			i = i + 1;
			calcula(i);
		}else
			return;
	}
}

e a main:

public class MainTeste {

	public static void main(String args[]){
		Gera x = new Gera();
		x.calcula(2);
	}
}


pelo q pude ver tu teve o TRABLHO CHATO de montar a pasta pra poder compilar. really thank’s men!!!
No fim de cada linha do teu codigo onde tive dúvida (2) coloquei minha pergunta. espero que apareça.

fernandosavio

public, private e protected são modificadores de acesso. Ou seja, especifica quem poderá acessar sua classe!
Eu coloquei public porque sempre coloco nas minhas classes de teste, nenhum motivo especial, mas estude os modificadores de acesso.

E troquei seu while por if por um motivo. Ou você faz isso com while ou com recursividade.
O While é para você ter um algoritmo repetido x vezes (que é especificado na condição do laço)…
A Recursividade também é para ser repetida x vezes, só que você especifica esse critério de parada em um if (que no caso foi para mostrar apenas 20 elementos do vetor).

Quando eu compilei seu código com while ele entrou em pane! heheheh…
Imagina só:

  • Você chamou o método calcula(esse vai ser o método pai);
  • o método calcula(pai) chamou 20 métodos calcula(filho);
  • cada um dos 20 metodos calcula(filho) chamou 20 calcula(neto)…
  • Deu pra entender né? Entrou em looping infinito!

A recursão, didáticamente falando, é composta pelo seguinte:

  • Um IF com o critério de parada (senao entra em looping infinito);
  • E o else com o que você quer fazer.

É uma explicação bem porca mas quando você entender como funciona a recursividade vai conseguir formular coisa mais complexas…
Era isso, espero que tenha entendido, abraços.

R

Fernando: Explicação básica e facil de entender. thank’s men!!!
me impressiona q eu entrei 2 meses depois de ti nesses forum e tu sabe a lot of things mor than me! (or better: i don’t know anything!!)

fernandosavio

Comecei a aprender java no inicio do ano cara!
Comecei com um professor de faculdade muito bom que me ensinou muito sobre OO. E eu corri muito atrás! Existem muitos materiais na internet e a documentação java ajuda muito… é só entender como funcionam as classes e interfaces que tu começa a entender tudo sozinho…
Qualquer coisa é só chama por MP que eu respondo!
Abração!

R

fernandosavio:
Comecei a aprender java no inicio do ano cara!
Comecei com um professor de faculdade muito bom que me ensinou muito sobre OO. E eu corri muito atrás! Existem muitos materiais na internet e a documentação java ajuda muito… é só entender como funcionam as classes e interfaces que tu começa a entender tudo sozinho…
Qualquer coisa é só chama por MP que eu respondo!
Abração!

Ok men realy thank’s!
Por acaso o professor era o neri ?
pra que serve “MP” mesmo ? (olha nub de novo hehehe)

R

e ja esta trab na area friend? - qse um ano de java acho q ja da pra conseguir algo se estudar todos dias e tiver um pouco de talento ne?

fernandosavio

MP = mensagem pessoal…
Estou trabalhando com PHP, javascript e um projeto separado em VB.NET. O Java mesmo que eu queria nao tem nada ainda…
Não é Neri o professor não. ehehheeh

WellingtonRamos

Ternário é uma forma de atribuir um valor ou outro conforme uma determinada regra.

Ou seja, é para um uso muito específico.
Exemplo: int variavel = 0; if(condicao) { variavel = 1; } else { variavel = 2; }
Neste exemplo, variavel é inicializada com zero. De acordo com uma condição específica, se a mesma for verdadeira, é atribuido 1; se for falsa, é atribuído 2.
Neste contexto, podemos alterar para um ternário ( o operador ternário é representado por ?: )
Exemplo convertido:

int variavel = 0; variavel = condicao ? 1 : 2; ou int variavel = condicao ? 1 : 2; //A inicialização foi suprimida, neste exemplo é desnecessário.

O valor que fica entre ? e : deve ser do mesmo tipo que o que fica entre : e ;.

Não é permitida mais que uma instrução em cada parte do ternário, ou seja, o exemplo abaixo não é permitido.

WellingtonRamos

if(b>500){ //O número 500 é o critério de parada da recursão return 0; //Aqui simplesmente encerra com a recursão, não nenhum efeito relevante nos cálculos }else{ System.out.println(a); //Imprime no console o elemento atual return calculaFibonacci(b, a+b); //Chama recursivamente o cálculo dos próximos elementos }
Coloquei só a parte que interessa :wink:

Pensando nos seguintes modelos:

//if if(CONDICAO) { variavel = RESULTADO_CASO_CONDICAO_VERDADEIRO; } else { variavel = RESULTADO_CASO_CONDICAO_FALSO; } //ternário variavel = CONDICAO ? RESULTADO_CASO_CONDICAO_VERDADEIRO : RESULTADO_CASO_CONDICAO_FALSO;

Considere que o System.out.println pode sair (ou seja, deve ser posto em outro lugar).
Faça as trocas.

Obs.: Onde lê "variavel = " pode ser trocado por return .

Tente montar o ternário agora.

WellingtonRamos

Cara,

Tenho a linha resolvida aqui. Só não postei pq o interesse é que você aprenda. Se teoricamente, você entendeu, não deve ser difícil resolver.
Como disse, montei a estrutura, é só trocar os bloquinhos. Teu único “problema” é onde vai ficar o Sysout. MAs isso te ajudo a resolver depois que você montar a linha do ternário.

if(b>500){ //CONDICAO return 0; //RESULTADO_CASO_CONDICAO_VERDADEIRO }else{ System.out.println(a); //tire isso daqui. return calculaFibonacci(b, a+b); //RESULTADO_CASO_CONDICAO_FALSO } //Coloque o return antes do ternário (não pode haver o return entre os sinais [b]?:;[/b])

Ternário é um pouco estranho mesmo, mas uma vez compreendido, fica muito simples :wink:

WellingtonRamos

fernandosavio:
Cara, o Wellington mastigou tudo pra você, não precisa nem pensar em nada é só pegar o código acima completar as lacunas no código abaixo:

return CONDICAO ? RESULTADO_CASO_CONDICAO_VERDADEIRO : RESULTADO_CASO_CONDICAO_FALSO ;

E eu tenho a apostila da Caelum também… É sim, um desafio, mas se você quer fazer em uma linha você não conseguirá imprimir!
E é um desafio estranho, porque qualquer programador que veja um código desses em uma linha já chutaria a canela de quem fez isso! Dar manutenção em código bruxo é fogo!

Consegue imprimir sim :wink:
Existem malícias no ternário que só Beelzebuth pra agradecer :twisted:
Essa desse exercício é simples. Fica, inclusive, elegante hehe.

Só pra exemplificar HellCode, veja esse: I Love Ternary

WellingtonRamos

Você ao menos tentou montar a estrutura da forma que eu descrevi?

WellingtonRamos

rafaelczy:

eu penso que terei de ser algo mais ou menos assim:

class Fibonacci {
	int calcula(int a, int b){
		return (b>500) ? 0 : System.out.println(a) DAI CHAMA calcula(b, a+b);	
	}
}

mas foi me dito que nao pode duas instrições nem no TRUE nem no FALSE.


Sim, não pode mesmo. A idéia é quase essa. Tire o System.out.println(a) colocando-o na linha de cima primeiro.

int calcula(int a, int b){ System.out.println(a); return (b>500) ? 0 : calcula(b, a+b); }

Se quiser uma linha, alinhe os comandos e pronto, está tudo numa linha.

WellingtonRamos

Hehehe… nem me atentei se o resultado estava correto. Pois peguei a lógica montada e remodelei para ternário.
Mas o importante é que você achou a lógica que precisava.

WellingtonRamos

fernandosavio:
Assim dá pra fazer uma classe toda em uma linha!
eauheuhaheuuahe

É que, na minha opinião, a impressão do resultado não está inclusa nessa história de colocar numa linha só :wink:

WellingtonRamos

rafaelczy:
Bom galera, jamais pensei q iria encher 3 paginas de posts pra gerar esse fibonacci de todas formas pedidas (num de var livre, depois 2 var apenas, depois recursividade, depois ternario + recursividade + 1 linha só) ufsss… 7 dias morando no forum…
mas valeu
fixei legal recursividade e op ternario
parabens ai pros atores principais da comedia q ajudaram e determinaram o sucesso
Welligton nogueira e Fernando savio
a todos demais thank’s to!

After thousands of years in caelum apostila charpeter 4 finaly going to the charpter 5 :shock:

:thumbup:

Criado 29 de agosto de 2011
Ultima resposta 1 de set. de 2011
Respostas 77
Participantes 7