Problem mit Rekursion

[Ulfmann]

Hi Leute,

Ich häng an einer Übungsaufgabe zu Rekursion. Ich soll da nix abgeben und mach's aus freien Stücken, weil ich das kapieren will und muss. Die berühmte Aufgabe mit den Fibonacci Zahlen krieg ich hin, der Algorithmus lässt sich auch leicht begreifen.

Hier mein Problem:

A prime number is an integer that cannot be divided by any integer other than one and itself. For example, 7 is prime because its only divisors are 1 and 7. The integer 8 is not prime because its divisors are 1, 2, 4, and 8.

Another way to define prime is:

prime(N) = prime(N, N-1)

prime(N, 1) = true

prime(N, D) = if D divides N, false

else prime(N, D-1)

For example,

prime(4) = prime(4,3)

prime(4,3) = prime(4,2)

prime(4,2) = false

Another example,

prime(7) = prime(7,6)

prime(7,6) = prime(7,5)

prime(7,5) = prime(7,4)

prime(7,4) = prime(7,3)

prime(7,3) = prime(7,2)

prime(7,1) = true

Translate the math-like definition of prime into two Java methods that return boolean. Use the % operator to test divisibility. Put your method into a class, write a testing class, and test your program.

Aufgabenstellung ist also, eine Zahl n zu überprüfen, ob sie eine Primzahl ist - und zwar rekursiv auf Teilbarkeit durch alle ihre Vorgänger.

Bisher hab ich das hier:

public class Recursion 

{

        public boolean prime( int n)

	{

		if (n == 1)

			return true;


		if((n % n-1) != 0 )

			return prime(n-1);


		else

			return false;

	}

}

public class RecursionTest

{

	public static void main(String args[])

	{


		Recursion prm = new Recursion();

		boolean isDivisible = prm.prime(4);

		System.out.print("Primzahl: " );

		if (isDivisible == true)

			System.out.print("ja");

		else

			System.out.print("nein");

	}

}

Dass es so nicht funktioniert, ist mir klar, nur ich hab keine Ahnung wie ich die prime() Methode richtig schreiben soll. Kann mir wer weiter helfen?

Vielen Dank schonmal.

[Klotzkopp]

Du brauchst zwei prime-Methoden, eine mit einem und eine mit zwei Parametern.

[Ulfmann]

So ungefähr dann?! Damit bekomm ich aber n StackOverFlow. Aber is die Richtung richtig?

	public boolean prime( int n)

	{


		if(n > 2)

			return prime(n, n-1);

		else if (n == 2)

			return true;


		else

			return false;

	}


	public boolean prime(int n, int d)

	{

		if(n % d == 0)

			return prime(1);

		else

			return prime(n, n-1);

	}

[DominikJ]

public class Prime {


	public Prime() {}


	private long divisor = 0;


	public static void main(String[] args) {

		Prime p = new Prime();

		long start = System.currentTimeMillis();

		boolean isDivisible = p.testPrime(151);

		System.out.print("Primzahl: ");

		if (isDivisible == true)

			System.out.println("Ja");

		else

			System.out.println("Nein, Erste Teilbarkeit durch "+p.getDivisor());


		System.out.println(System.currentTimeMillis()-start+" ms");

	}


	public boolean testPrime(long n) {

		return testPrime(n, n-1);

	}

	public boolean testPrime(long n,long d) {

		if (d == 1)

			return true;


		if ((n % d) != 0)

			return testPrime(n, d-1);


		else

			setDivisor(d);

			return false;

	}


	public long getDivisor() {

		return divisor;

	}


	public void setDivisor(long divisor) {

		this.divisor = divisor;

	}


}

So in etwa.

Edit:

Kannst das ganze natürlich auch Iterativ machen.

Is glaub ich sogar sinnvoller und nicht so Fehleranfällig

Edit 2: Wollte grad Iterativ posten, aber war ja zum lernen hier. Dann lass ich das lieber

Bearbeitet 14. April 2009 von DominikJ
Iterativ

[Ulfmann]

Ja vielen Dank für die Hilfe, hat mich auch weiter gebracht. Meine Lösung is allerdings noch um einiges kürzer und verständlicher geworden:

public class Recursion 


{

	public boolean prime(long n) 

	{

		if(n == 1)

			return false;


		return prime(n, n - 1);

	}


	private boolean prime(long n, long m) 

	{

		if (m == 1) 

		{

			return true;

		} 

		else if (n % m == 0)

		{

			return false;

		} 

		else 

		{

			return prime(n, m - 1);

		}

	}

}

public class RecursionTest

{

	public static void main(String args[])

	{


		Recursion prm = new Recursion();

		boolean isDivisible = prm.prime(4);

		System.out.print("Primzahl: " );

		if (isDivisible == true)

			System.out.print("ja");

		else

			System.out.print("nein");

	}

}

Und na klar wäre es mit ner herkömmlichen Schleife einfacher, aber es ging ja grad um Rekursion.

Danke nochmal.