Additions mittels Rekursion

[Moviefreak]

Hi,
ich bin Anfänger in Sachen Java-Programmierung und habe folgendes Problem:

Ich soll eine rekursive Methode schreiben, die zwei Zahlen mit einander addiert, ohne da man ein Additionszeichen benutzt. Allerdings ist eine Successorfunktion erlaubt.

Bis jetzt habe ich folgendes gemacht:

public class Aufgabe {
//Successor-Funktion
	public static int successor(int s){
		return s+1;
	}

//Addition zweier Zahlen - rekursiv
	public static int addition(int r,int s,int v){
		if (v == s){
			return r;
		}
		else {
			successor(r);
			successor(v);
			return addition(r,s,v);
		}
	}

public static void main(String[] args) {

//Zufallszahlen zwischen 1 und 50 in Array einlesen
		int n = 10 ;
		int array[] = new int[n];                            
		for (int i = 0; i < n; i++)                         
		   array[i] = (int)Math.floor((Math.random() * 50) + 1);

//Endrekursiv Ausgabe der Summe zweier Zahlen m>=0 und n>=0
int v = 0;
System.out.println("Summe rekursiv: "+ addition(r,s,v));
	}
}

Allerdings kommt es zu einem StackOverflow in der Methode addition, vielleicht kann mir da jemand helfen und sagen woran das liegt!

Vielen Dank im Voraus!

 

[ttplayer]

Wenn du zwei Zahlen addieren willst, warum übergibst du dann 3 Parameter?
Außerdem macht das

successor(v);

ja gar nichts, du musst den Rückgabewert schon abfangen.

 

[Moviefreak]

Gute Frage erschien mir dir einzige Lösung ,wenn man 2 Zahlen miteinander addieren soll ohne Addition benutzen zu dürfen. Quasi ein Variable die mitzählt und wenn man dann die eine Zahl so lange um 1 erhöht bis man die andere erreicht, sollte man doch auf das Ergebnis kommen. Für alternative Vorschläge bin ich natürlich offen.

THX ttplayer

Das hat mir sehr geholfen! Soweit habe ich mal wieder nicht gedacht.

 

[ttplayer]

Also, eine Zählervariable musst du doch nicht als Parameter übergeben:

public int add(int a, int b)
{
    for (int z = 0; z < b; z++)  a = successor(a);
    return a;
}

 

[ttplayer]

achso, rekursiv:

public int add(int a, int b)
{
    if(b > 0) return add(successor(a), --b);
    else return a;
}

 

[Moviefreak]

OK das sieht wesentlich schöner aus...ich merke da muss ich noch sehr viel Arbeit investieren!

Danke!

 

[Apokalypse]

Ich weiß ja nicht,wieso so man so was Rekursiv lösen soll.
Aber ich wollte, mich auch mal dran versuchen:

 private static int add(int a,int b)
 {	
	if(b==0)
	    return a;
	return add( (a) - (-b),0);
 }

P.S Ich hoffe du meintest mit Additionszeichen nur Plus^^

 

[ttplayer]

Das ist zwar regelkonform, aber nur für die geschriebenen, nicht für die ungeschriebenen

 

[Apokalypse]

ungeschriebene == successor(a) ?
Oder worauf beziehst du dich^^

 

[Marco13]

P.S Ich hoffe du meintest mit Additionszeichen nur Plus^^

private static int add(int a,int b)
{	
    return a - (-b);
}

:toll:

Mal im ernst: Sowas wie x++ oder a-b oder so ist da eigentlich nicht. Mal mein Lösungsvorschlag - ein bißchen obfuskiert, aber garantiert +- und --frei

class RekursionAufgabe
{
    //Successor-Funktion
    public static int successor(int s){
        return s+1;
    }

    //Addition zweier Zahlen - rekursiv
    public static int addition(int a, int b)
    {
        return _(a,b,0,0,0);
    }

    public static int _(int _){return successor(_);}
    public static int _(int i, int í, int î, int ì, int l)
    {
        return i==î?í==ì?l:_(i,í,î,_(ì),_(l)):_(i,í,_(î),ì,_(l));
    }


    public static void main(String[] args) {

        System.out.println("Summe rekursiv: "+ addition(0,0));
        System.out.println("Summe rekursiv: "+ addition(1,0));
        System.out.println("Summe rekursiv: "+ addition(0,2));
        System.out.println("Summe rekursiv: "+ addition(23,19));
    }
}

EDIT: In der Hoffnung, dass in der Original-Aufgabenstellung von positiven Zahlen die Rede war - sonst müßte man das noch anpassen...

 

[ttplayer]

ungeschriebene == successor(a) ?
Oder worauf beziehst du dich^^

auf
a+b = a -(-b)

 

[Ein Keks]

man könnts auch so machen xD :

public class Test{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int i = scan.nextInt();
		int j = scan.nextInt();

		System.out.println(confusingAddition(i, j));
	}

	public static int confusingAddition(int a, int b){
		a = Integer.MIN_VALUE - (Integer.MAX_VALUE-a-b) - 1;
		return a;
	}
}

ok im endeffekt ist das nur a+b mit sinnlosen drumherum aber vielleicht fällst nicht auf xDD

 

[Landei]

Einfach und ineffizient:

public class Addition {

    public static int succ(int n) {
        return n+1;
    }

    public static int pred(int n) {
        if (n == 0) throw new IllegalArgumentException();
        return predHelp(0,n);
    }

    private static int predHelp(int k, int n) {
        return succ(k) == n ? k : predHelp(succ(k),n);
    }

    public static int add(int a, int b) {
        return a == 0 ? b : add(pred(a), succ(b));
    }

    public static void main(String[] args) {
        System.out.println(add(11,89));
    }

}

 

[Marco13]

(So als Tipp: Meine Lösung ist ungefähr das, was rauskommt, wenn man alle Methoden von Landei's Lösung in eine einzige reinwurstet )

 

[Landei]

We need no stinkin' ints:

public class AddNat {
   private static class Nat {
       private final static Nat ZERO = new Nat(null);
       private final Nat pred;
       public Nat(Nat pred) { this.pred = pred;  }
       public Nat succ(){ return new Nat(this); }
       @Override public String toString() {
           int i = 0;
           for(Nat n = this; n != ZERO; n = n.pred) {
               i++;
           }
           return "" + i;
       }
       @Override public boolean equals(Object o) {
           if(o instanceof Nat) {
               Nat that = (Nat) o;
               if(this == ZERO) {
                   return that == ZERO;
               } else {
                   return this.pred.equals(that.pred);
               }
           } else {
               return false;
           }
       }
   }

    public static Nat pred(Nat n) {
        if (n == Nat.ZERO) throw new IllegalArgumentException();
        return predHelp(Nat.ZERO, n);
    }

    private static Nat predHelp(Nat k, Nat n) {
        return k.succ().equals(n) ? k : predHelp(k.succ(), n);
    }

    public static Nat add(Nat a, Nat b) {
        return a.equals(Nat.ZERO) ? b : add(pred(a), b.succ());
    }

    public static void main(String[] args) {
        System.out.println(add(Nat.ZERO, Nat.ZERO));
        System.out.println(add(new Nat(Nat.ZERO),Nat.ZERO));
        System.out.println(add(Nat.ZERO, new Nat(new Nat(Nat.ZERO))));
        System.out.println(add(new Nat(new Nat(new Nat(Nat.ZERO))),new Nat(new Nat(Nat.ZERO))));
    }

}

 

[Apokalypse]

So, ich fand die Sache jetzt so spannend.
Dass, ich ein Volladdierer implementiert habe, der nutzt garantiert keine Aritmetik mittels +/-.. Operator.
Die Addition wird mit Logischer Algebra implementiert. Man kann an einem Volladdierer sehr gut erkennen wie eine CPU 2 Zahlen addiert.
In der Realität ist das eine, Sammlung aus Transistoren welches die logischen Operatoren übernehmen aber in hier sollte ein Software Lösung als Veranschaulichung genügen.

So damit ich auch mal posen kann:

/**
 * Implementierung eines Volladdierers
 * @author Apokalypse
 * @version 20 November 09
 */

/**
 * Implementierung eines Volladdierers
 */
public class VollAddierer {

    public static void main(String[] args) {
    	//Teste die Addition/Subtraktion:
    	VollAddierer calc = new VollAddierer();
    	long a = 2;
    	long b = 6;
    	long result = calc.add(a,b);
 
    	if(a+b == result)
    		System.out.println("Volladdierer: " + a +" + "+ b + " = " + result);
    	else
    		System.out.println("Volladdierer: " + a +" + "+ b + " != " + result + " => " + (a+b));
    	
    	a = 5;
    	b = 6;
    	result = calc.sub(a,b);
    	if(a-b == result)
    		System.out.println("Volladdierer: " + a +" - "+ b + " = " + result);
    	else
    		System.out.println("Volladdierer: " + a +" - "+ b + " != " + result + " => " + (a-b));
    }
    /**
     *  Standard Konstruktor
     */
    public VollAddierer(){};
    

    /**
     *  Addition mittels Logischer Algebra </br>
     *  Vorgehensweise, wie beim Volladdierer
     * @param a Zahl a
     * @param b Zahl b
     * @return a+b
     */
    public long  add(long a,long b) 
    {	
    	return addImpl(a,b,false,(byte)0,0);
    }
    
    /**
     * 
     *  Subtraktion mittels Logischer Algebra </br>
     *  Vorgehensweise, wie beim Volladdierer 
     * @param a Zahl a
     * @param b Zahl b
     * @return a-b
     */
    public long sub(long a,long b)
    {	
    	return addImpl(a,-b,false,(byte)0,0);
    }
    /**
     * Implementierung der Addition mittels Logischer Algebra</br>
     * In Form einer Rekursiven Funktion.
     * @param a Zahl a
     * @param b Zahl b
     * @param carryBit Übertragsbit
     * @param stelle Index des ersten Bits => 0
     * @param result initial Wert für das Ergebnis
     * @return a+b
     */
    private long addImpl(long a,long b,boolean carryBit,byte stelle,long result) throws IllegalArgumentException
    {	
    	
    	if(a==0)
    		return b;
    	if(b == 0)
    		return a;
    	//Stelle wurde korrekt gesetzt?
    	if(result == 0)
        	checkStelleValue(stelle,true);
    	// Alle Bits gesetzt?
    	if(stelle==Integer.SIZE)
    		return result;
    	
    	//Bits an stelle x ermitteln 
    	boolean aBit = getBit(a,stelle);
    	boolean bBit = getBit(b,stelle);
    	//Brechnen des Binären Addition, beachtung des CarrayBits
    	boolean resultBit = aBit ^ bBit ^ carryBit;
    	//Übertrag berechnen
    	carryBit = (aBit & carryBit) | (bBit & carryBit) | (aBit & bBit);
    	//ResultBit setzen und BitStelle 
    	return addImpl(a,b,carryBit,(byte)( stelle+1 ),setBit(result, resultBit, stelle));
    	
    }
    /**
     *  Gibt den Wert, eines Bits, einer Zahl zurück</br>
     * @param Zahl
     * @param stelle Position des gewünschten Bits
     * @return Bit Wert
     */
    public boolean getBit(long zahl,byte stelle) throws IllegalArgumentException
    {
     long indicatorBit = calcIndicatorBit(stelle);
	 return ((zahl & indicatorBit) == indicatorBit? 1:0) == 1;
    }
    /**
     *
     * Setzt den Wert, eines Bits, einer Zahl</br>
     * @param zahl Zahl
     * @param bit Wert des Bits
     * @param stelle Position des gewünschten Bits
     * @return geänderte Zahl
     */
    public long setBit(long zahl,boolean bit,byte stelle) throws IllegalArgumentException
    {
    	long indicatorBit = calcIndicatorBit(stelle);
    	if(bit)
    		zahl |= indicatorBit;		// 1 setzen
    	else
    		zahl &= ~indicatorBit;		// 0 setzen
    	return zahl;
    }
    /**
     * Gibt eine Zahl zurück bei dem, nur das Bit an der Position <i>stelle</i> gesetzt ist.</br>
     * @param  Position des gesetzten Bits
     * @return Zahl mit gesetztem Bit, an Position  <i>stelle</i> 
     */
    public long calcIndicatorBit(byte stelle) throws IllegalArgumentException
    {	
    	checkStelleValue(stelle,false);
    	//Berechnen des IndexBits: 0001 <-stelle 1, 0010 <-stelle 2,0100 <-stelle 3,...
    	return  1<<stelle;
    }
    
    private void checkStelleValue(byte stelle,boolean startAdd) throws IllegalArgumentException
    {
    	if(stelle<0 || stelle > Long.SIZE)
    		if(startAdd)
    		   throw new IllegalArgumentException("'stelle' expect a value equals 0");	
    		else
    		   throw new IllegalArgumentException("'stelle' expect a value between 0 and " + Long.SIZE);
    }
    
}