Aprendendo recursividade

Programação Java
#41

[quote=sowyer][quote=rafaelczy][quote=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![/quote]

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?[/quote]

Exato ! :thumbup: [/quote]
Então qdo q recursividade é uma escolha ideal de código, se ela gasta mais memoria e processador?

#42

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

#43

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:

#44

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:

#45

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

#46

[quote=sowyer]rapz!.. vc chama o calcula e não passa o parâmetro ?? pq ?

[/quote]
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” ?

#47

[code]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 ;  
}

}[/code]

#48

[quote=fernandosavio][code]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 ;  
}

}[/code][/quote]
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

#49

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…

#50

[quote=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…[/quote]
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?

#51

[code]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);
	}
}

}[/code]

#52

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…

#53

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

[code]

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

		gera.calcula(2);	
}

}[/code]

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

#54

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

#55

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?

#56

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?

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

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);
			}
		}
}
#59

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

#60

[quote=rafaelczy]porem me falaram que:
compila mas-

[code]
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);
		}
	}

}
[/code][/quote]
me disseram q meus comandos print nao executam dentro metodo construtor gera(){} - Pq e como devo fazer ?
Fernando, o que sao conceitos OO ?