Recursão

Pessoal tem como me ajudarem a entender essa maldita recursao ja debuguei fiz tudo mas nao consigo entender pq pra mim o retorno seria 2 :frowning:

[code]public static void main(String[] args) {

	int n = ff(7);
	
	System.out.println(n);
	
}


public static int ff(int n){
	
	//System.out.println(n);
	
	if(n == 1){
		return 1;
	}
	
	if((n % 2) == 0){
		
		return ff(n/2);
		
	}
	
	return ff((n - 1)/2) + ff((n+1)/2);
	
}[/code]

Até onde eu consigo entender, pra ver se alguem consegue me ajudar:

ff(7) retorna ff(3)
ff(3) retorna ff(1)
ff(1) retorna 1. Então acaba a primeira recursao

depois nao consigo entender o que ocorre na segunda :cry:

Então vamos por partes:

Começa com 7.
Como 7 é impar vai retornar ff(3) + ff(4)

Pegando no 3
Como 3 é impar vai retornar ff(1) + ff(2)

Pegando no 1
Pelo if, retorna 1

Pegando no 2
É par, retorna ff(1)

Pegando no 1
Pelo if, retorna 1

Temos então que ff(3) igual 1 + 1 = 2

Voltando acima ff(7) = 2 + ff(4)

Pegando no 4
É par, retorna ff(2)

Pegando no 2
É par, retorna ff(1)

Pegando no 1
Pelo if, retorna 1

Então, ff(4) = 1

Voltando acima, ff(7) = 2 + 1 = 3

O retorno é então 3 e não 2.

[code]Então vamos por partes:

Começa com 7.
Como 7 é impar vai retornar ff(3) + ff(4)

Pegando no 3
Como 3 é impar vai retornar ff(1) + ff(2)

Pegando no 1
Pelo if, retorna 1

Pegando no 2
É par, retorna ff(1)

Pegando no 1
Pelo if, retorna 1
[/code]

se ff(1) retorna 1 e ff(2) retorna ff(1) que retorna 1, entao 1+1 = 2. Porque volta?

Esse 2 ainda é só o ff(3)

Como chamaste com ff(7), ele chama: return ff((n - 1)/2) + ff((n+1)/2); que é ff(3) + ff(4)

[quote=pmlm]Esse 2 ainda é só o ff(3)

Como chamaste com ff(7), ele chama: return ff((n - 1)/2) + ff((n+1)/2); que é ff(3) + ff(4)[/quote]

ff3) + ff(4)

ff(1) + ff(2)

f(1) retorna 1 ff(2) retorna ff(1) que retorna 1.

pmlm desculpa nao esta entendendo o que vc quer me passar mas e pq esta dificil pra mim. Minha dificuldade e essa que quando um lado da recursao retorna 1 termina no outro tb termina nao entendo da onde sai +1.

A) ff(7) = ff(3) + ff(4)

B) ff(3) = ff(1) + ff(2)

C) ff(4) = ff(2)

Substituindo em A:

D) ff(7) = [ff(1) + ff(2)] + ff(2)

E) ff(1) = 1

F) ff(2) = ff(1) (que ja sabemos que é 1)

Substituindo em D:

ff(7) = [1+1]+1 = 3

primeiro nao é executado esse lado return ff((n - 1)/2) + para depois ir para o outro?

Sim, mas isso para perceberes as operações feitas, a ordem é:

ff(7)
ff(3)
ff(1)
ff(2)
ff(1)
ff(4)
ff(2)
ff(1)

[quote=pmlm]Sim, mas isso para perceberes as operações feitas, a ordem é:

ff(7)
ff(3)
ff(1)
ff(2)
ff(1)
ff(4)
ff(2)
ff(1)[/quote]

Hum, então acho que estou começando a entender.

ff(7)
return ff((n - 1)/2) +

ff(3)
return ff((n - 1)/2) +

ff(1)
return 1 - MOOOOORREEU ESSE LADO NÉ?

Vamos para o outro lado

ff(7)
return ff((n + 1)/2) +

Agora nao seria

ff(4) ?
que retornaria ff(n/2)

ff(2)
que retornaria ff(n/2)

ff(1)
return 1 e acabaria aqui?

O que terminou foi o primeiro lado do ff(3) ainda falta o segundo lado do ff(3)

Imagina que tens uma pilha com os ff a calcular.

Colocas ff(7)

Retiras ff(7) e colocas ff(3) + ff(4)

Retiras o ff(3) e colocas ff(1) + ff(2) -> fica ff(1)+ ff(2) + ff(4)

Retiras o ff(1) e sabes que é 1 -> fica 1 + ff(2) + ff(4)

Retiras o ff(2) e colocas ff(1) -> fica 1 + ff(1) + ff(4)

Retiras o ff(1) e sabes que é 1 -> fica 1 + 1 + ff(4)

Retiras o ff(4) e colocas ff(2) -> fica 1 + 1 + ff(2)

Retiras o ff(2) e colocas ff(1) -> fica 1 + 1 + ff(1)

Retiras o ff(1) e sabes que é 1 -> fica 1 + 1 + 1

Não tens mais ff a calcular e tens o resultado 3

[code]Colocas ff(7)

Retiras ff(7) e colocas ff(3) + ff(4)

Retiras o ff(3) e colocas ff(1) + ff(2) -> fica ff(1)+ ff(2) + ff(4) [/code]
mas da onde ta saindo esse ff(2).

return ff((n - 1)/2) + ff((n+1)/2);

para n = 3

[quote=pmlm] return ff((n - 1)/2) + ff((n+1)/2);

para n = 3[/quote]

Entao estou entendendo tudo errado entao =/

para todos “n” é executado esssas duas recursoes return ff((n - 1)/2) + ff((n+1)/2); ? não era uma de cada vez? Essa ff((n - 1)/2) depois + essa ff((n+1)/2); ?

Caracoliss entendi agora pml depois de tantas horas lendo e relendo kkk. Muito obrigado viu velho?!

Para todos os n não, só para os ímpares (que não o 1). Para os pares é return ff(n/2)

Entendi pmlm muito obrigado.

Agora eu troquei o exemplo veja só:

[code]package pacote.testando;

import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class B extends A{

public static void main(String[] args) {   
    
    int n = ff(4);   
       
    System.out.println(n);   
       
}   
   
   
public static int ff(int n){   
       
   //System.out.println(n);   
       
    if(n == 1){   
        return 1;   
    }   
       
    if((n % 2) == 0){   
           
        ff(n/2);   // Tirei o return.
           
    }   
       
    return ff((n - 1)/2) + ff((n+1)/2);   
       
}  

}[/code]

ff(4)
ff(2)
ff(1)
return 1.

Depois queo retorno é 1, porque o metodo continua?

Sem o return, o código vai continuar até apanhar um return e vai devolver return ff((n - 1)/2) + ff((n+1)/2); para os pares também.

Entao quando retorna 1 não era pra sair do método?