Warum terminiert die Ackermannfunktion bei ack(1,3) mit 5?

[Coolbininet]

Hallo Leute!

Warum terminiert diese Funktion mit 5 (obige Angaben)!

#include <stdio.h>

int ack(int n, int m)
{
	int temp;

	if ((n<0)||(m<0)) return -1;
	if (n==0) return m+1;
	if (m==0) return ack(n-1,1);

	temp=ack(n, m-1);
	return ack(n-1,temp);
}

int main ()
{
	ack(1,3);
	printf ("%d",ack);
}

Bitte um Visiualisierung und verständliche Erklärung!

Grüsse Coolbininet

[c.rackwitz]

ack(n,m):
    n<0 or m<0        -1
    n = 0             m+1
    m = 0             ack(n-1, 1)
    sonst             ack(n-1, ack(n, m-1))

ack(1, 3)
ack(0, ack(1, 2))
ack(0, ack(0, ack(1, 1)))
ack(0, ack(0, ack(0, ack(1, 0))))
ack(0, ack(0, ack(0, ack(0, 1))))
ack(0, ack(0, ack(0, 2)))
ack(0, ack(0, 3))
ack(0, 4)
5

edit: es gibt verschiedene ackermannfunktionen.
daneben gibt es noch "hyper", bei dem +, *, ^,... logisch fortgesetzt wird. hier meine ueberlegung und implementation in scheme

(define hyper
  (lambda (n a b)
    (cond ((= n 0) (+ a 1)) ; (~ means increment) a~b = a+1, no basis, only for n=0
          ((= n 1) (+ a b)) ; basis
          ((= n 2) (* a b)) ; speedup
          (#t
           (let loop ((i (- b 1)) (r a))
             (if (<= i 0)
                 r
                 (loop (- i 1)
                       (hyper (- n 1) r a))))))))

[CStoll (off)]

Kurz: Weil die Ackermann-Funktion an dieser Stelle den Wert 5 hat
(Du kannst dir den Ablauf gerne am Aufruf-Stack mitverfolgen)

a(0,m) = m+1
a(n+1,0) = a(n,1)
a(n+1,m+1) = a(n,a(n+1,m))

a(1,3) = a(0,a(1,2))
       = a(1,2)+1
       = a(0,a(1,1))+1
       = a(1,1)+2
       = a(0,a(1,0))+2
       = a(1,0)+3
       = a(0,1)+3
       = 1+1+3
       = 5

[Coolbininet]

Aber es steht ja nirgends, wenn 5 erreicht ist, dass es (zB) mit if und exit beendet wird! Ich kann leider mit den Zeichnungen nichts anfangen, tut mir leid!

Bitte um weitere Hilfe!

Grüsse Coolbininet

[c.rackwitz]

geht ja nur weiter, wenn zum ergebnis wieder die ackermannfunktion benutzt wird...
frag eventuell lieber deinen mathelehrer...

[CStoll (off)]

Coolbininet schrieb:

Aber es steht ja nirgends, wenn 5 erreicht ist, dass es (zB) mit if und exit beendet wird!

Die wird auch nicht mit exit beendet (das schießt das gesamte Programm ab), sondern mit return.

[Coolbininet]

Und mit welchen Return genau?

Grüsse Coolbininet

[c.rackwitz]

Coolbininet: nimm dir ein lexikon (wikipedia z.b.) und schlage dieses wort nach:
"rekursion"

[net 0]

ackermannfunktion? nie gehört. wofür braucht man das?

[SG1]

Die Ackermannfunktion ist _das_ Beispiel f"ur eine nicht primitiv-rekursive Funktion.

[net 0]

SG1 schrieb:

Die Ackermannfunktion ist _das_ Beispiel f"ur eine nicht primitiv-rekursive Funktion.

das ist alles? hat wohl nur theoretische bedeutung oder kann man die praktisch für irgendwas einsetzen?

[c.rackwitz]

sie steigt nur wie bloed und ist mehrfach rekursiv. schon mit kleinen argumenten steigt sie quasi ins unberechenbare oder ueberhaupt darstellbare.

[net 0]

c.rackwitz schrieb:

sie steigt nur wie bloed und ist mehrfach rekursiv. schon mit kleinen argumenten steigt sie quasi ins unberechenbare oder ueberhaupt darstellbare.

na toll

[c.rackwitz]

http://de.wikipedia.org/wiki/Ackermannfunktion

jetz soll ich schon linksklave spielen oder was? ich lass mich gleich entmodden, dann seid ihr erloest...

[ackermann]

Bitte bleib uns treu.

[ethereal]

Coolbininet schrieb:

Hallo Leute!
Warum terminiert diese Funktion mit 5 (obige Angaben)!

Weil die Ackermann-Fkt. terminiert. Wieso sollte sie auch nicht?
Das einzig Besondere an ihr ist die Tatsache, dass sie die erste Fkt. war, die nicht auf primitiv-rekursive Fkt. zurückführbar ist und schneller wächst als jede bekannte primitiv rekursive Fkt.
Das bedeutet aber nicht, dass sie nicht terminieren würde. Die Anzahl der Berechnungsschritte steigt halt nur enorm an.