Hallo,

meine Frage ist folgende:

Gilt eine Funktion nur dann als geschachtelt, wenn sie sich selber aufruft, und dabei auch als Argument übergeben wird,
oder
reicht es aus, wenn sie eine andere Funktion (rekursiv oder nicht) aufruft, bei der sie ein oder mehrere Argumente stellt?

Eine Funktion ist rekursiv, wenn sie in ihrer Definition (direkt oder indirekt) vorkommt.

Eine Funktion ist rekursiv, wenn sie in ihrer Definition (direkt oder indirekt) vorkommt.

aber wie sieht es aus mit einer verschachtelter Rekursion?

Eine Funktion, die irgendeine andere Funktion einfach so aufruft, ist m.E. nicht rekursiv, z.B.:

(define (square x)
(multiply x x))

Es geht eher um

(define (square x)
(multiply (square x) x))

Jo, das ist rekursiv.

Hehe, du bist mir echt n Spaßvogel :D

Ist es rekursiv geschachtelt? Handelt es sich um geschachtelte Rekursion?

Fred, die Frage war über eine geschachtelt rekursive Funktion. Ich verstehe nähmlich auch nicht, wann genau ein rekursiver Aufruf geschachtelt ist.

Ach so. Den Begriff hatte ich vorher noch nie gehört. Nach ein bischen googeln scheint es so, dass eine Funktion sich selbst aufruft, und zwar mit einem Parameter, der auch wieder die Funktion aufruft.

Wenn also innerhalb der Definition von f ein Term der Art f(f(x)) auftaucht.

(define (f x) (if (<= x 1) 2 (+ 1 (f (- (f (- x 1)) 1)))))      Rekursionsverankerung ^       ^ geschachtelter Rekursionsschritt
So verstehe ich das. Jetzt sollte auch die Endlosschleife eliminiert sein.

Okay, dem zufolge wäre

(define (square x)
(multiply (square x) x))

keine geschachtelte Rekursion.

Vielen Dank

Nach dem SE3 Skript (WS 2007/08)

Definition 57 (Geschachtelte Rekursion ). Eine Rekursion ist geschachtelt,
wenn die Funktion in der rekursiven Verwendung selbst als Argument mitge-
geben wird.

Da es "in der rekursiven Verwendung" (also Funktion ruft sich selbst auf) als Argument kommt ist obiges Beispiel

(define (square x)
(multiply (square x) x))

meiner Meinung nach nicht geschachtelt rekursiv, aber

(define (sqare x) (square (square x) x)[Ja, ist jetzt eine Endlosschleife, aber übersichtlich ;)]
ist geschachtelt rekursiv.

Aber Danke für die Frage, hatte das auch erst anders verstanden [22]

was aber, wenn multiply wieder square aufruft, und als parameter multiply mit übergibt, dann wäre das ja ersteinmal eine indirekte Rekursion, und eigentlich doch auch geschachtelt, quasi indirekt geschachtelt.

Bsp.:
(define (square x)
(multiply (square x) x))
(define (multiply x y)
(square (multiply (- x 1) (- y 1)))

Das ist nur indirekt (square->multiply und multiply->square) und direkt (square->square, multiply->multiply). Damit es geschachtelt wird muss es nach meinem Verständnis Argument vom eigenen Aufruf sein.

Also,
sowas wie
(define (foo x)
(bar (foo x)))
(define (bar x)
(foo (bar x)))
ist (mal abgesehn von einer Endlosschleife) eine indirekte Rekursion, und keine verkettete. Dafür hätte sich die Funktion in der Definition selbst aufrufen _und_ als argument übergeben müssen:
(define (another-foo x)
(another-foo (another-foo x)))
ist also eine verschachtelte Rekursion. Anders kommt keine verschachtelte Rekursion zustande.