Recursividade de decomposição

[aalmeid]

Boas pessoal, tenho um problema em mãos. Basicamente é fazer a decomposição de nºs de forma recursiva

ex:

4 = 2*2

6 = 2*3

12 = 2*2*3

16 = 2*2*2*2

25 = 5 * 5

...

Basicamente fiz o seguinte, e funciona perfeitamente

import static java.lang.System.*;

public class FactorsIterativo
{
   public static void main(String[] args)
   {
   if (args.length == 0)
	   exit (0);
      
      for(int i = 0; i < args.length; i++) {
         out.print(args[i]+" = "+factors(Integer.parseInt(args[i])));

	 int valor = Integer.parseInt(args[i]);
	 int divisor = factors (Integer.parseInt (args[i]));
         int calc = valor / divisor;

	 do{
		if (calc == valor || calc == 1)
			break;
		out.print (" * "+factors(calc));
		divisor = factors(calc);
		calc = calc / divisor;
	}while (true);
	out.println();
  }
   }
   
   public static int factors (int temp) {
   if (temp % 2 == 0) {
	   return 2;
   }
   
   if (temp % 3 == 0) {
	   return 3;
   }
   
   if (temp % 5 == 0) {
	   return 5;
   }
   else
	return temp;
   }
}

Problema é que não é recursivo.

Estive voltas e voltas com isto e não consegui pensar numa forma recursiva para fazer isto.

Basicamente a condição é simples mas não estou mesmo a ver como fazer com que os nºs sejam retornados dentro da função "factors"

Queria que me explicassem como fazer e não o código sff.

cumps

[HappyHippyHippo]

public static void recur(int valor) {
  int temp = 0;

  if ((temp = factors(valor)) == valor) {
    out.print (valor);
  } else {
    recur(valor/temp);  
    out.print (" * "+temp);
  }
}

[KTachyon]

public static int factors (int temp) {
   if (temp % 2 == 0) {
	   return 2;
   }
   
   if (temp % 3 == 0) {
	   return 3;
   }
   
   if (temp % 5 == 0) {
	   return 5;
   }
   else
	return temp;
   }

Tendo em conta este método, presumo que só queiras decompor números inferiores a 49, certo? É que sem testares com outros números primos, não vais muito longe.

Repara que se testares a divisão a partir do valor mais pequeno (2) e fores incrementando, consegues obter sempre a decomposição em números primos. Claro que existem outros métodos mais eficientes, mas isso é uma coisa que podes optimizar depois.

[aalmeid]

Tendo em conta este método, presumo que só queiras decompor números inferiores a 49, certo? É que sem testares com outros números primos, não vais muito longe.

Repara que se testares a divisão a partir do valor mais pequeno (2) e fores incrementando, consegues obter sempre a decomposição em números primos. Claro que existem outros métodos mais eficientes, mas isso é uma coisa que podes optimizar depois.

Boas, com este método, consigo decompor nº superiores (e bem superiores) a 49...

Executei o programa com nºs grandes e devolveu:

1500 = 2 * 2 * 3 * 5 * 5 * 5

2495 = 5 * 499

36987 = 3 * 12329

165254 = 2 * 82627

...

Parece estar realmente a funcionar.

Já agora, obrigado HappyHippyHippo vou analizar essa função para poder estudar melhor a recursividade

cumps

[HappyHippyHippo]

Boas, com este método, consigo decompor nº superiores (e bem superiores) a 49...

experimenta 88

[aalmeid]

experimenta 88

output

88 = 2 * 2 * 2 * 11

[KTachyon]

Tipo... Não consegues decompor o 49... Só por aí já falha.

Queres mais exemplos?

77

91

119

121

143

E garanto-te que podia passar aqui o dia a gerar números...

E, já agora, podes decompor 82627 (em 53 * 1559).

[aalmeid]

Tipo... Não consegues decompor o 49... Só por aí já falha.

Queres mais exemplos?

77

91

119

121

143

E garanto-te que podia passar aqui o dia a gerar números...

E, já agora, podes decompor 82627 (em 53 * 1559).

ah já entendi... já percebi. Obrigado 😉

[aalmeid]

btw alguém sabe/arranja problemas de recursividade? tenho alguns mas já os fiz e andei a pesquisar no google e maior parte é para calcular os nº de fibonacci, nº de Lucas, factorial, ...

Se alguém souber onde posso arranjar mais exercícios, se puder dizer agradecia 😉

cumps

[HappyHippyHippo]

podes alterar 90% das soluções iterativas para recursivas ...

mas tenho um intrinsecamente recursivo : quicksort

[aalmeid]

Uma dúvida que me surgiu agora.

A recursividade começa do fim para o inicio. Por exemplo

3! = 3 * 2!

2! = 2 * 1!

e depois lança o valor de 1! = 1, 2! = 2 * 1; 3 ! = 3 * 2 = 6

Se quisesse imprimir estes passos, ele iria imprimir do fim para o inicio. Ou melhor, iria imprimir o 1, depois o 2 e só depois o 6.

Como faço para alterar essa ordem?

Não queria colocar aqui directamente o código pq o problema não é bem sobre factorial mas sim sobre a listagem de ficheiros, mas no meu caso faz do fim para o início. Existe alguma forma de imprimir "correctamente"?

[HappyHippyHippo]

depende da ordem que chamas as funções:

nao testei mas acho que da diferente

int fact1(int i) {
  int result = 0;
  printf(" %d ", i);
  if (i == 1) {
    return 1;
  } else {
    return i * fact1(i-1);
  }
}

int fact2(int i) {
  int result = 0;
  if (i == 1) {
    printf(" %d ", i);
    return 1;
  } else {
    printf(" %d ", i);
    return i * fact1(i-1);
  }
}

[aalmeid]

Já consegui. Fiz desta forma:

public static void nFiles (File fin) {
	File [] list = null;
	int file = 0;

	if (fin.isDirectory())
		list = fin.listFiles();

	for (int i = 0; i < list.length; i++)
	{
		if (list[i].isFile() || list[i].isDirectory())
			file++;

		if (i == list.length)
			break;
	}
	System.out.println (fin.getPath()+": "+file+" files");

	for (int i = 0; i < list.length; i++)
		if (list[i].isDirectory())
			nFiles(list[i]);
}