Weinga-Unity Entrekursivierung

Algorithmen-Demo

Entrekursion rekursiver Algorithmen

Weichinger Klaus - snaky.1@gmx.at - http://www.Weinga-Unity.at.tt

1. Tschebyschew-Polynom

a) Der rekursive Algorithmus

Der rekursive Algorithmus ist wie folgt definiert:

float T(↓int n  ↓float y) {
  if (n==0) return 1
  if (n==1) return y
  return=2*y*T(↓n-1 ↓y) - T(↓n-2 ↓y)
}

b) Vorbereitung

Hier werden die rekursiven Aufrufe in einzelnen Zeilen aufgeteilt und in den Variablen T1 und T2 zwischengespeichert. Weiters wird noch eine Änderung vorgenommen, sodass nur mehr eine return-Anweisung existiert.

float T(↓int n  ↓float y) {
  float result, T1, T2
  if(n<2) {
    if(n==0) { result=1 }
    else { result=y }
  }else{
    T1=T(↓n-1 ↓y)
    T2=T(↓n-2 ↓y)
    result=2*y*T1-T2
  }
  return result
}

c) Automatenstruktur

Dabei wird bei jedem rekursiven Aufruf der Algorithmus in einen neuen Zustand unterteilt (1..3).

float T(↓int n  ↓float y) {
  float result=0, T1=0, T2
  float result
//****************************************
//                                  (1) **
  if(n<2) {
    if(n==0) { result=1 }
    else { result=y }
  }else{
    result=T(↓n-1 ↓y)
//                                      **
//****************************************
//                                  (2) **
    T1=result
    result=T(↓n-2 ↓y)
//                                      **
//****************************************
//                                  (3) **
    T2=result
    result=2*y*T1-T2
  }
//                                      **
//****************************************
  return result
}

Nun wird der Algorithmus so gestalltet, dass die Zustände mit einer Schleife nacheinander durchlaufen werden. Er ist aber immernoch rekursiv!

float T(↓int n  ↓float y) {
  float result=0, T1=0, T2
  int state=1
  boolean loop=true
  while(loop) {
    switch(state) {
//****************************************
//                                  (1) **
      case 1:  if(n<2) {
                 if(n==0) { result=1 }
                 else { result=y }
                 loop=false
               }else{
                 result=T(↓n-1 ↓y)
                 state=2
               }
//                                      **
//****************************************
//                                  (2) **
      case 2:  T1=result
               result=T(↓n-2 ↓y)
               state=3
//                                      **
//****************************************
//                                  (3) **
      case 3:  T2=result
               result=2*y*T1-T2
               loop=false
//                                      **
//****************************************
    }
  }
  return result
}

d) Entrekursivierung

Nun wird der Algorithmus entrekursiviert, indem ein rekursiver-Aufruf durch ein sichern der lokalen Variablen in einen Stack-Speicher bzw. ein return eines rekursiven Algorithmuses durch ein zurückladen der lokalen Varialben aus dem Stack ersetzt wird.

// Benötigte Funktionen

void initStack() {
  // Diese Funktion initialisiert einen für die Entrekursion benötigten
  // Kellerspeicher und leert diesen. Der Type (int, float, ...) der zu
  // verwaltenden Objekte ist beliebig.
}

void push(↓n) {
  // Push kellert den Wert n im Kellerspeicher (Stack) ein.
  // Der Typ von n ist beliebig.
}

void pop(↑n) {
  // Pop ließt einen Wert aus dem Kellerspeicher aus und
  // liefert diesem im abgespeicherten Type zurück.
}

boolean emptyStack() {
  // liefert true, wenn der Kellerspeicher leer ist und
  // false, wenn der Kellerspeicher nicht leer ist
}

float T(↓int n  ↓float y) {
  float result=0, T1=0, T2
  int state=1
  boolean loop=true
  initStack()
  while(loop) {
    switch(state) {
      case 1:  if(n<2) {
                 if(n==0) { result=1 }
                 else { result=y }
                 if(emptyStack()) {
                   loop=false
                 }else{
                   pop(↑state); pop(↑T1); pop(↑n)
                 }
               }else{
                 push(↓n); push(↓T1); push(↓2)
                 n=n-1
                 state=1
               }

      case 2:  T1=result
               push(↓n); push(↓T1); push(↓3)
               n=n-2
               state=1

      case 3:  T2=result
               result=2*y*T1-T2
               if(emptyStack()) {
                 loop=false
               }else{
                 pop(↑state); pop(↑T1); pop(↑n)
               }
    }
  }
  return result
}

Schreibtischtest

#	n	y	loop	state	result	T1	T2	Stack
1	2	2	true	1	0	0	0	202
2	1	2	true	1	2	0	0	202
3	2	2	true	2	2	0	0	leer
4	2	2	true	2	2	2	0	223
5	0	2	true	1	2	2	0	223
6	0	2	true	1	1	2	0	223
7	2	2	true	3	1	2	0	leer
8	2	2	true	3	1	2	1	leer
9	2	2	false	3	7	2	1	leer

→ Ergebnis = 7
Der Stack wird von rechts befüllt bzw. von rechts ausgelesen.
Die einzelnen Schritte repräsentieren nicht einen fixen Break-Point im Algorithmus sondern werden erzeugt, wenn Änderungen erfolgt sind. Im 2. Beispiel wurde ein Schreibtischtest gemacht, der immer die Zustände vor dem Schleifendurchlauf eingetragen wurden.

2. Graphen

a) Rekursiver Algorithmus

Lösungsidee

Der Algorithmus liefert 1, wenn k=1 ist. Ist k>1, liefert er k mal die Anzahl der Knoten eines Unterzweiges plus k Konten von sich selbst.

Implementierung in Jana

int nodes(↓int k) {
  if (k==1) {
    return 1
  }else{
    return k*nodes(↓k-1)+k
  }
}

b) Entrekursivierung

Vorbereitung

// nur 1 rekursiver Aufruf pro Zeile 
// und direkte Return Anweisungen beseitigt 
int nodes(↓int k) {
  int result, k1
  if (k==1) {
    result=1
  }else{
    k1=nodes(↓k-1)
    result=k*k1+k
  }
  return result
}

Automatenstruktur

// Schritte getrennt durch rekursive Aufrufe 
int nodes(↓int k) {
  int result, k1
//****************************************
//                                  (1) **
  if (k==1) {
    result=1
  }else{
    result=nodes(↓k-1)
//                                      **
//****************************************
//                                  (2) **
    k1=result
    result=k*k1+k
  }
//                                      **
//****************************************
  return result
}

// Schleifen einbauen 
int nodes(↓int k) {
  int result, k1
  int state=1
  boolean loop=true
  while(loop) {
    switch(state) {
//****************************************
//                                  (1) **
      case 1:
          if (k==1) {
            result=1
            loop=false
          }else{
            result=nodes(↓k-1)
            state=2
          }
//                                      **
//****************************************
//                                  (2) **
      case 2:
          k1=result
          result=k*k1+k
          loop=false
//                                      **
//****************************************
    }
  }
  return result
}

Entrekursivieren

// Benötigte Funktionen

void initStack() {
  // Diese Funktion initialisiert einen für die Entrekursion benötigten
  // Kellerspeicher und leert diesen. Der Type (int, float, ...) der zu
  // verwaltenden Objekte ist beliebig.
}

void push(↓n) {
  // Push kellert den Wert n im Kellerspeicher (Stack) ein.
  // Der Typ von n ist beliebig.
}

void pop(↑n) {
  // Pop ließt einen Wert aus dem Kellerspeicher aus und
  // liefert diesem im abgespeicherten Type zurück.
}

boolean emptyStack() {
  // liefert true, wenn der Kellerspeicher leer ist und
  // false, wenn der Kellerspeicher nicht leer ist
}

int nodes(↓int k) {
  int result, k1
  int state=1
  boolean loop=true
  initStack()
  while(loop) {
    switch(state) {
      case 1:
          if (k==1) {
            result=1
            if(emptyStack()) {
              loop=false
            }else{
              pop(↑state); pop(↑k)
            }
          }else{
            push(↓k); push(↓2)
            k=k-1
            state=1
          }

      case 2:
          k1=result
          result=k*k1+k
          if(emptyStack()) {
            loop=false
          }else{
            pop(↑state); pop(↑k)
          }
    }
  }
  return result
}

Schreibtischtest für k=4

#	k	loop	state	result	K1	Stack
1	4	true	1	0	0	leer
2	3	true	1	0	0	42
3	2	true	1	0	0	4232
4	1	true	1	0	0	423222
5	2	true	2	1	0	4232
6	3	true	2	4	1	42
7	4	true	2	15	4	leer
8	4	false	2	64	15	leer

→Ergebnis=64 für k=4
Der Stack wird von rechts befüllt und von rechts wieder ausgelesen.
Jeder Eintrag entspricht dem Zustand vor jedem Schleifendurchlauf.

c) Iterativer Algorithmus

Lösungsidee

Die Berechnung erfolgt auf einem Bildungsgesetz, wobei die Anzahl der Knoten von n=1..k nacheinander berechnet werden. Ein schneller, einfacher und übersichtlicher iterativer Algorithmus ist somit möglich (siehe Implementierung).

Implementierung in Jana

int nodes(↓int k) {
  int result=0
  for(int i=1..k) {
    result=i*result+i
  }
  return result
}