Informatik zum Donnerstag

[Rolf B]

Hallo Camping_RIDER,

ok, ich fühlte mich herausgefordert 😀

Mich hat allerdings an der Aufgabe genervt, dass der Typ "Nat" Operatoren als externe Funktionen implementieren soll, was mit sich bringt, dass man ständig Typabfragen machen muss. Das ist nicht objektorientiert. Ich habe die Implementierung daher in Methoden statt Funktionen geändert, delegiere fleißig und kann so Polymorphie statt Typabfragen nutzen.

Allerdings zerstöre ich so wohl jeden Gedanken an eine Tailrekursion. Ob die mit einer function-Implementierung eher möglich ist? Vielleicht verstehe ich Tailrekursion ja auch nicht.

function sum1To(n) {
   return n == 0 ? 0 : n + sum1To(n-1);
}

Das ist eine rekursive Version der "Summe von 1-n" Schleife, selbst da wüsste ich nicht wie man das tail-rekursiv machen soll weil ja das Ergebnis der vorigen Rekursion noch verarbeitet werden muss. Jedenfalls komme ich da bis n=11379 bevor der Stack überläuft.

Was ist hiermit:

function bar(sum: number, n: number) : number {
  return n == 0 ? sum : bar(sum + n, n-1);
}

DAS sollte doch tail-rekursiv sein; aber von wegen - da bricht schon bei 10431 ab. Also noch anders:

function bar(sum: number, n: number) : number {
  if (n == 0) return sum;
  sum += n;
  n--;
  return bar(sum, n);
}

Nun komme ich bis 12517, bevor der Stack überläuft. Das war Chrome 81 - welche JS Engine kennt denn überhaupt Tailrekursion?!

Die Funktion from (oder to?), die den numerischen Wert eines Nat ausgibt, hielt ich - weil ja DEBUG - auch nicht für so toll und ich habe den Objekten daher ein Property debugValue gegeben. Und eine Minus-Operation habe ich auch eingebaut - aber die poste ich nicht.

Aufgabe für euch: Baut "Minus", aber bitte ohne Typtests, nur mit Polymorphie.

Dass ich hier eine mögliche rekursive Lösung für Aufgabe 1 poste, sollte wohl ok sein - der induktive Teil ist ja das Kernproblem.

class Zero  {
  readonly debugValue: number = 0;
  plus(m: Nat) : Nat { return m; } 
  mult(m: Nat) : Nat { return new Zero(); } 
  fac() : Nat { return new Succ(new Zero()); }
}
class Succ  {
  readonly pred: Nat;
  readonly debugValue: number; 
  constructor(pred: Nat) {
    this.pred = pred;
    this.debugValue = pred.debugValue + 1;
  }
  plus(m: Nat) : Nat { return this.pred.plus(new Succ(m)); }
  mult (m: Nat) : Nat { return m.plus(this.pred.mult(m)); }
  fac() : Nat { return this.mult(this.pred.fac()); }
}

Diese Lösung bricht bei to(9).fac() ebenfalls ab. Es ist egal, ob man this.mult(this.pred.fac()) oder this.pred.fac().mult(this) rechnet - die auf Addition zurückgeführte Multiplikation bringt beim Berechnen von 403209 oder 940320 einen Stackoverflow.

Die induktive Lösung muss ich noch anschauen. Ich muss vermutlich erstmal kapieren, was "induktiv" im Gegensatz zu "iterativ" überhaupt bedeuten soll...

Rolf