Grundlagen der funktionsorientierten Programmierung mit SCHEME/Superminimum

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
Eine endständig rekursive  Minimumsuche haben wir bei den [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Komplexe Anwendungen: Numerische Listen#Kleinstes Listenelement|komplexen Anwendungen zu (unverschachtelten) numerischen Listen]] implementiert:

<code id="50c91a91b1878">
(define minimum1
  (lambda (ls)
    (cond
      [(null? (cdr ls)) (car ls)]
      [(< (car ls) (cadr ls)) (minimum1 (cons (car ls) (cddr ls)))]
      [else
       (minimum1 (cdr ls))])))
</code>

<run id="50c91a91b1b62">
(minimum1 '(22 35 45 13 8 7 8 6 14 12 47))
</run>

Dieser Algorithmus lässt sich mit Mehrfachrekursionen auf verschachtelte numerische Listen anwenden:

<code id="50c91a91b199a">
(define superminimum1
  (lambda (ls)
    ...))
</code>

<check>
(and (= (superminimum1 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47))) 6)
     (= (superminimum1 '(22 35 45 13 8 7 8 6 14 12 47)) 6)
     (= (superminimum1 '(22)) 22))
</check>

<run id="50c91a91b1bc9">
(superminimum1 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47)))
</run>

Die Prozedur <tt>minimum2</tt> stellt eine weitere Implementation der Minimumsuche in unverschachtelten numerischen Listen dar. Sie demonstriert die Leistungsstärke echtrekursiver Problemlösungen:

<code id="50c91a91b1a10">
(define minimum2
  (lambda (ls)
    (cond
      [(null? (cdr ls)) (car ls)]
      [else
       (let ([min (minimum2 (cdr ls))])
         (if (< (car ls) min)
             (car ls)
             min))])))
</code>

<run id="50c91a91b1c33">
(minimum2 '(22 35 45 13 8 7 8 6 14 12 47))
</run>

Auf dieser Basis lässt sich das "Superminimum" noch einfacher und eleganter realisieren:

<code id="50c91a91b1a77">
(define superminimum2
  (lambda (ls)
    ...))
</code>  

<check>
(and (= (superminimum2 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47))) 6)
     (= (superminimum2 '(22 35 45 13 8 7 8 6 14 12 47)) 6)
     (= (superminimum2 '(22)) 22))
</check>

<run id="50c91a91b1cd0">
(superminimum2 '(22 35 (45 13 (8 (7 8) (6) 14) 12 47)))
</run>

Zurück zu [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Mehrfachrekursionen|Mehrfachrekursionen]].