Rekursion in Iterative umwandeln

[Buttahbrot]

Hallo,

ich habe folgende Aufgabe bekommen: Ich soll eine Methode so umschreiben, das keine Rekursion mehr vorhanden ist, sie also iterativ gelöst wird. Die Methode sieht folgendermaßen aus:

static int meth(int n){
		if(n < 10){
			return 1;
		} else{
			return meth(n / 10) + meth(n - 1);
		}
	}

Die ist ziemlich simpel, ihr wird ein n übergeben und damit wird rekursiv gerechnet. Nun muss ich dies Iterativ schreiben, mein Ansatz sieht wie folgt aus:

	static int iterative(int n){
		int n1 = n;
		
		if(n < 10){
		return 1;
		}else{
			for(int i = 0; i <= n; i++){
				n = (n1/10) + (n1-1)/10 + (n1-2)/10;
			}
		}
		return n;
	}

Dies ist bis jetzt noch nicht wirklich funktionsfähig und ich habe schon mehrere Stunden daran rumprobiert bevor ich meine Frage hier posten wollte.

Ich hoffe jemand kann mir bei meinem Problem helfen.

MfG Buttahbrot

 

[pro2]

Hab jetzt auch mal 'ne Zeit rumprobiert, leider ohne Erfolg, bin wohl zu blöd.

    static int methIt(int n)
    {
        int temp, sum = 0;
        ArrayList<Integer> list = new ArrayList();
        list.add(n);
        while (!list.isEmpty())
        {
            if ((temp = list.remove(0)) >= 10)
            {
                list.add(temp / 10);
                list.add(temp - 1);
            }
            else
            {
                sum++;
            }
        }
        return sum;
    }

Das war einfach - aber wohl nicht das, was gesucht ist.^^

 

[xehpuk]

Du hast einen Ansatz und du hast mehrere Stunden herumprobiert.
Meine Frage ist dann: Wie bist du vorgegangen, um zu diesem Ansatz zu kommen?
Wenn ich so eine Aufgabe hätte, würde ich mich als Erstes fragen, was die Methode genau macht. Wenn man das weiß, ist eine iterative Umsetzung eigentlich trivial.

 

[Buttahbrot]

Hallo und danke schonmal für die Antworten,

das ich die Methode falsch verstehe war mein erster Gedanke, deswegen habe ich eigentlich sehr viel rumprobiert, da ich dachte irgendwann auf das richtige Ergebnis kommen zu müssen. So wirklich sicher bin ich mir immer noch nicht ob ich Sie nun verstanden habe, aber wahrscheinlich eher nicht wenn ich nicht auf die richtige Lösung komme
So wie ich das sehe wird die Methode erstmal mit n/10 gerechnet, was ((n/10) + (n-1)/10) wäre, und anschließend mit n-1, was folgendem entsprechen würde: ((n-1)/10 + (n-2)/10).

MfG Buttahbrot

 

[pappawinni]

Das Ding fächert sich auf wie ein Baum, weil sich die Funktion bei jedem Schritt zweimal selbst aufruft
und wenn jeweils die Abbruchbedingung erreicht ist, wird das gewissermassen von den Blättern her aufgelöst.
Eine Mehrfach-Rekursion. Nicht wirklich trivial das Ganze.

 

[Buttahbrot]

Genau so in etwa habe ich mir das auch mal gedacht, nur weiß ich nicht genau wie ich das schreiben soll, da das Programm ja für jedes beliebige n funktionieren soll. Nur weiß ich nicht wie ich das jetzt machen soll, weil ich, zumindest so wie ich es mir gerade vorstelle, einen endlos-code schreiben müsste^^

 

[Niggel595]

Moin,

versuch erstmal, die Fibonacci-Folge iterativ zu berechnen. Dabei wird im Prinzip das gleiche Prinzip benutzt. Ich geb dir grad mal die rekursive Fibonacci-Folge:

int fib(int n){
    if(int n<2){
        return 1;
    } else {
        return fib(n-2)+fib(n-1);
    }
}

Wenn du das iterativ schaffst, solltest du das ganze auf dein Problem übertragen können.

Den iterativen Code für dein Problem hab ich jetzt erst mal nicht dazugeschrieben, nach Möglichkeit solltest du es ja selbst hinbekommen

LG
Niggel

 

[Gnutella]

Hast du die Aufgabe inzwischen lösen können? Da ich das selbst auch ganz interessant fand, hier meine Lösung für das Problem:

Spoiler: Solution

	static int methIt(int n) {
	   int result=1;
	   if(n > 9) {
	      int[] values = new int[n / 10 + 1];
	      for (int i=0; i<10; i++) {values[i] = 1;}
	      int methDiv10;
          int methMinus1;
			 			
		  for (int i=10; i <= n; i++) {
		     methMinus1 = result;
		     methDiv10 = values[i / 10];
		     result = methDiv10 + methMinus1;  
		     if (i < values.length) {values[i] = result;}
		  }
	   }
	   return result;
	}

 

[Bleiglanz]

Spoiler: Oder gleich alle Daten speichern

    static int methit(int n){
        int res[] = new int[n+1];
        for(int j=1;j<=n;j++){
            res[j] = (j<10) ? 1 : res[j/10]+res[j-1]; 
        }
        return res[n];
    }

 

[JohannisderKaeufer]

@Bleiglanz probiere doch mal

methit(-1);