SOLVIUM

Programmierung

Primfaktorzerlegung in tScheme - rekursiv

Der Code

Diesmal setzen wir die Primfaktorzerlegung rekursiv um. Neben der Primfaktorzerlegung auf imperative Art ist der rekursive Ansatz schöner, da "natürlicher".

(define (primfaktoren n)
  (if
    (not (number? n)) (throw "function[primfaktoren] expects a number argument.")
    (<= n 0)          (throw "function[primfaktoren] expects a number greater than or equal to null.")
    (primfaktoren-h '() n 2)
  )
)

(define (primfaktoren-h l n i)
  (if (= n 1) l
      (= 0 (mod n i)) (primfaktoren-h (concat l (list i)) (/ n i) 2)
      (primfaktoren-h l n (+ i 1))
  )
)

Die Funktionsweise

Die Implementierung besteht aus zwei Funktionen. Zunächst wird die Hauptfunktion primfaktoren definiert. In ihr wird eine Überprüfung des übergebenen Parameters n auf Gültigkeit (Zahl > 0) durchgeführt und schließlich die Hilfsfunktion primfaktoren-h aufgerufen.

Diese Hilfsfunktion ist endrekursiv, das heißt, das Ergebnis der Rekursion wird ständig "mitgeschleppt" und am Ende der Auswertung durch die Funktionen "herausgereicht" (schön mit trace nachzuvollziehen). Die Vorgehensweise innerhalb der Funktion ist leicht zu erklären, sie erwartet drei Parameter: Das bisherige Ergebnis l, die zu zerlegende Zahl n und einen Zähler i.

Wenn die zu zerlegende Zahl 1 ist, wird das Ergebnis ausgegeben. Sonst wird die Zahl auf Teilbarkeit durch i geprüft.

  • Ist sie (glatt) teilbar, wird i zu den Ergebnissen hinzugefügt (concat ...) und die Primfaktorzerlegung erneut für n geteilt durch i durchgeführt.
  • Ist n nicht glatt durch i teilbar, wird die Funktion erneut mit einem um 1 erhöhten i aufgerufen.

Problematisch an der obigen Implementierung ist vielleicht, dass die Hilfsfunktion so direkt aufrufbar ist. Eine Möglichkeit wäre, sie nur innerhalb von primfaktoren lokal zu definieren, was aber der Übersichtlichkeit schadet, weshalb hier darauf verzichtet wird.

Der Aufruf

*** tScheme, Version 2.7 ***
To quit, type `(quit)` or Ctrl-D (Linux), Ctrl-C (Windows)

-> (load "primfaktoren-rekursiv.s")
function[primfaktoren]
-> (primfaktoren 42)
(2 3 7)
->

© 2006-2019 Solvium.de - Impressum

» Blog powered by Wordpress. Silk icons von FamFamFam.