Fachkonzept: Rekursive Funktionsaufrufe
Rekursion in Racket
Rekursion ist eine Problemlösestrategie, in der sich eine Funktion selbst aufruft.
Diesen Aufruf nennen wir einen Rekursionsschritt. Durch jeden Rekursionsschritt wird das Problem
auf ein kleineres, strukturgleiches Teilproblem heruntergebrochen, bis ein Basisfall erreicht wird,
für welchen das Problem direkt lösbar ist. Das Erreichen des Basisfalls löst das Gesamtproblem entweder direkt
oder es kann anschließend schrittweise durch Nutzung der Teillösung gelöst werden.
Zur Implementierung einer rekursiven Funktion benötigt man die folgenden Komponenten:
- Test, ob der Basisfall erreicht wurde
- Lösung des Basisfalls
- Rekursiver Aufruf als Rekursionsschritt
select-index
, die das Element einer Liste l
am übergebenen Index i
liefert:
(define select-index (lambda (l i) (cond ([= i 0] (first l)) (else (select-index (rest l) (- i 1))))))