home Grundlagen der Funktionalen Programmierung: Rekursive Funktionen Prof. Dr. Uwe Schmidt FH Wedel
Kapitelübersicht
List ComprehensionInhaltsverzeichnisFunktionen höherer Ordnung

Rekursive Funktionen

weiter
weiter

Rekursion
In der Definition einer Funktion wird diese Funktion selbst wieder verwendet.
weiter
Beispiel
factorial :: Integer -> Integer
 
factorial n
  | n == 0  = 1                      -- 1. Regel
  | n >  0  = n * factorial (n - 1)  -- 2. Regel
merke
Partielle Funktion
weiter
Auswertung
  factorial 3
={ 2. Regel }
  3 * factorial 2
={ 2. Regel }
  3 * (2 * factorial 1)
={ 2. Regel }
  3 * (2 * (1 * factorial 0))
={ 1. Regel }
  3 * (2 * (1 * 1))
={ rechnen }
  3 * (2 * 1)
={ rechnen }
  3 * 2
={ rechnen }
  6
weiter
Terminierung
Durch rekursive Definitionen werden Terminierungsbeweise einfach.
Beweis durch Induktion
weiter
2. Beispiel
Definition von (*) durch (+)
 
(*) :: Num a => a -> a -> a
 
m * n
  | n == 0 = 0                     -- .1
  | n >  0 = m + (m * (n - 1))     -- .2
  | n <  0 = negate (m * negate n) -- .3
weiter
Auswertung
  3 * 2
={ .2 }
  3 + (3 * (2 - 1))
={ rechnen }
  3 + (3 * 1)
={ .2 }
  3 + (3 + (3 * (1 - 1)))
={ rechnen }
  3 + (3 + (3 * 0))
={ .1 }
  3 + (3 + 0)
={ rechnen }
  3 + 3
={ rechnen }
  6
merke
In den Beispielen gibt es pro Regel höchstens einen rekursiven Aufruf
weiter
Beispiel
für mehrere rekursive Aufrufe: Quicksort
weiter
2. Beispiel
für mehrere rekursive Aufrufe
 
fib :: Num a => a -> a
 
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
weiter
gut
Die mathematische Definition der Fibonacci-Folge kann 1-1 in ein ausführbares Programm umgesetzt werden
schlecht
Dieser Algorithmus zur Berechnung der Fibonacci-Zahlenfolge ist so ineffizient, dass er in praktischen Anwendungen unbrauchbar ist.
schlecht
Die Laufzeit steigt exponentiell mit der Größe von n
weiter
Aufrufgraph für fib 5
with thanks to Brent Yorgey for the diagrams package
weiter
Effiziente Implementierung
mit einer linearen Laufzeit
 
fib2 :: Num a => a -> a
 
fib2 = fib' 0 1
  where
    fib' x0 x1 0 = x0
    fib' x0 x1 n = fib' x1 (x0 + x1) (n - 1)
weiter
Wechselseitige Rekursion
Indirekte Rekursion über mehrere Funktionen
Beispiel
Test auf gerade/ungerade
 
even :: Int -> Bool
even 0 = True
even n = odd (n - 1)
 
odd :: Int -> Bool
odd 0 = False
odd n = even (n - 1)
weiter
schlecht
Randbemerkung:
even und odd sind nur partiell definiert.
weiter

Rekursion mit Listen

Konstruktion
von Listen
 
[]  ::             [a]  -- leere Liste
(:) :: a -> [a] -> [a]  -- cons
merke
Dieses sind die einzigen Funktionen, mit denen Listen konstruiert werden können.
merke
Alle anderen Funktionen mit Listen als Resultat-Typ werden auf diese beiden Funktionen zurück geführt.
merke
Konstruktor-Funktionen, kurz Konstruktoren, dürfen in Mustern verwendet werden.
merke
Mit Konstruktoren in Mustern können Listen wieder auseinander genommen werden.
merke
Listen verarbeiten besteht aus dem Auseinandernehmen von Listen und der Verarbeitung der Elemente.
Beispiel
vordefinierte Funktion product
 
product :: Num a => [a] -> a
 
product []       = 1              -- .1
product (i : is) = i * product is -- .2
weiter
Auswertung
  product [2, 3, 4]
={ Def. Listen }
  product (2 : (3 : (4 : [])))
={ .2 }
  2 * product (3 : (4 : []))
={ .2 }
  2 * (3 * product (4 : []))
={ .2 }
  2 * (3 * (4 * product []))
={ .1 }
  2 * (3 * (4 * 1))
={ rechnen }
  2 * (3 * 4)
={ rechnen }
  2 * 12
={ rechnen }
  24
2. Beispiel
vordefinierte Funktion length
 
length :: [a] -> Int
 
length []       = 0
length (i : is) = 1 + length is
weiter
3. Beispiel
vordefinierte Funktion reverse
 
reverse :: [a] -> [a]
 
reverse []       = []
reverse (x : xs) = reverse xs ++ [x]  -- (x : [])
weiter
4. Beispiel
vordefinierte Funktion (++)
 
(++) :: [a] -> [a] -> [a]
 
[]       ++ ys = ys              -- .1
(x : xs) ++ ys = x : (xs ++ ys)  -- .2
weiter
Auswertung
  [1, 2] ++ [3, 4, 5]
={ Def. Listen }
  (1 : (2 : [])) ++ (3 : (4 : (5 : [])))
={ .2 }
  1 : ((2 : []) ++ (3 : (4 : (5 : []))))
={ .2 }
  1 : (2 : ([] ++ (3 : (4 : (5 : [])))))
={ .1 }
  1 : (2 : (3 : (4 : (5 : []))))
={ Def. Listen }
  [1, 2, 3, 4, 5]
weiter
Beispiel
Einfügen in aufsteigend sortierte Listen
 
insert :: Ord a => a -> [a] -> [a]
 
insert x []       = [x]              -- .1
insert x (y : ys)
  | x <= y        = x : (y : ys)     -- .2
  | otherwise     = y : insert x ys  -- .3
weiter
Auswertung
  insert 3 [1, 2, 4, 5]
={ .3 }
  1 : insert 3 [2, 4, 5]
={ .3 }
  1 : (2 : insert 3 [4, 5])
={ .2 }
  1 : (2 : (3 : (4 : [5]))
={ Def. Listen }
  [1, 2, 3, 4, 5]
weiter
?
Einfügen ohne Duplikate?
weiter
Beispiel
Sortieren durch Einfügen
 
isort :: Ord a => [a] -> [a]
 
isort []       = []                  -- .1
isort (x : xs) = insert x (isort xs) -- .2
weiter
Auswertung
  isort [3, 2, 1, 4]
={ .2 }
  insert 3 (isort [2, 1, 4])
={ .2 }
  insert 3 (insert 2 (isort [1, 4]))
={ .2 }
  insert 3 (insert 2 (insert 1 (isort [4])))
={ .2 }
  insert 3 (insert 2 (insert 1 (insert 4 (isort []))))
={ .1 }
  insert 3 (insert 2 (insert 1 (insert 4 [])))
={ Def. insert }
  insert 3 (insert 2 (insert 1 [4]))
={ Def. insert }
  insert 3 (insert 2 [1, 4])
={ Def. insert }
  insert 3 [1, 2, 4]
={ Def. insert }
  [1, 2, 3, 4]
weiter
merke
Liste ist eine rekursive Datenstruktur
Verarbeitung mit rekursiver Funktion
weiter
merke
Liste bildet eine lineare Kette
Rekursion bildet eine lineare Aufrufkette
weiter
Schablone
für lineare Rekursion auf Listen
 
f :: [a] -> b
 
f []       = e1
f (x : xs) = x `op` f xs
gut
Fast alle Verarbeitungsfunktionen für Listen besitzen diese Struktur
schlecht
Es gibt (wenige) Ausnahmen
weiter
Beispiel
Gleichzeitige Verarbeitung mehrerer Listen
 
zip :: [a] -> [b] -> [(a, b)]
 
zip []       _        = []
zip _        []       = []
zip (x : xs) (y : ys) = (x, y) : zip xs ys
weiter
Anwendung
Zeilen durchnummerieren
 
numberLines :: [String] -> [(Int, String)]
 
numberLines xs = zip [1 .. length xs] xs
weiter
2. Beispiel
Rekursion mit Verarbeitung mehrerer Parameter
Aufgabe
Auf welche Arten kann man einen Euro in Cent-Münzen wechseln?
Ansatz
Verallgemeinerung der Aufgabenstellung
 
Auf welche Arten kann man einen beliebigen Geldwert mit einer Menge von vorgegebenen Münzen und Scheinen wechseln?
Lösung
Typ der Funktion
change :: Int -> [Int] -> [[Int]]
Beispiele
change 1 [5, 2, 1] = [[1]]
change 2 [5, 2, 1] = [[2], [1,1]]
change 4 [5, 2, 1] = [[2,2], [2,1,1], [1,1,1,1]]
 
-- Randfälle
change   0  [5, 2, 1] = ???
change (-1) [5, 2, 1] = ???
change   5  []        = ???
change   0  []        = ???
Lösung
type Coins = [Int]
 
change :: Int -> Coins -> [Coins]
change n cs
  | n <  0 = []
  | n == 0 = [[]]
  | n >  0 = change' cs
  where
    change' []        = []
    change' (c : cs1) = [c : xs | xs <- change (n - c) cs]
                        ++
                        change n cs1
-- # of changes
 
numChanges :: Int -> Coins -> Int
numChanges n cs = length (change n cs)
merke
Geschachtelte Verzweigungen über die Parameter
merke
Fall zu komplex: Auslagern in Hilfsfunktion
weiter
Anwendung
Einen Euro wechseln
 
change1cent :: [Coins]
change1cent = change 1 [50, 20, 10, 5, 2, 1]
 
change2cent :: [Coins]
change2cent = change 2 [50, 20, 10, 5, 2, 1]
 
change10cent :: [Coins]
change10cent = change 10 [50, 20, 10, 5, 2, 1]
 
change1euro :: Int
change1euro = numChanges 100 [50, 20, 10, 5, 2, 1]
weiter
Tests
Eigenschaften der Resultate überprüfen
 
-- value remains the same
 
test1 :: Int -> Coins -> Bool
test1 n cs = all sumEqualsN (change n cs)
  where
    sumEqualsN xs = sum xs == n
 
-- only existing coins used
 
test2 :: Int -> Coins -> Bool
test2 n cs = all legalCoins (change n cs)
  where
    legalCoins xs = all (`elem` cs) xs
 
-- predefined
all  :: (a -> Bool) -> [a] -> Bool
 
sum  :: Num a => [a] -> a
 
elem :: Eq a  => a -> [a] -> Bool
merke
Notwendige Tests, NICHT hinreichende Tests
weiter
weiter

Konstruktion rekursiver Funktionen

Rezept
.1
Definiere den Typ der Funktion
.2
Zähle die Fallunterscheidungen auf,
jeder Fall wird durch eine Regel verarbeitet
.3
Definiere die Verarbeitung der einfachen Fälle, in denen das Resultat direkt berechnet werden kann
.4
Definiere die rekursiven Fälle
.5
Verallgemeinere und vereinfache
weiter
weiter

Beispiele zum Kapitel

   1module RecFct where
   2
   3import Prelude hiding ( length
   4                      , product
   5                      , reverse
   6                      , zip
   7                      , even
   8                      , odd
   9                      )
  10
  11import qualified Prelude as P
  12
  13factorial       :: Integer -> Integer
  14factorial n
  15    | n == 0    = 1
  16    | n >  0    = n * factorial (n - 1)
  17
  18
  19(.*.) :: Int -> Int -> Int
  20m .*. n
  21    | n == 0    = 0
  22    | n >  0    = m + (m .*. (n - 1))
  23
  24product          :: Num a => [a] -> a
  25product []       = 1
  26product (n : ns) = n * product ns
  27
  28length          :: [a] -> Int
  29length []       = 0
  30length (x : xs) = 1 + length xs
  31
  32reverse          :: [a] -> [a]
  33reverse []       = []
  34reverse (x : xs) = reverse xs ++ [x]
  35
  36(.++.)           :: [a] -> [a] -> [a]
  37[]       .++. ys = ys
  38(x : xs) .++. ys = x : (xs .++. ys)
  39
  40insert          :: Ord a => a -> [a] -> [a]
  41insert x []     = [x]
  42insert x (y : ys)
  43    | x <= y    = x : y : ys
  44    | otherwise = y : insert x ys
  45
  46isort           :: Ord a => [a] -> [a]
  47isort []        = []
  48isort (x : xs)  = insert x (isort xs)
  49
  50zip                     :: [a] -> [b] -> [(a, b)]
  51zip []        _         = []
  52zip _        []         = []
  53zip (x : xs) (y : ys)   = (x,y) : zip xs ys
  54
  55numberLines    :: [b] -> [(Int, b)]
  56numberLines xs = zip [1..length xs] xs
  57
  58fib   :: Integer -> Integer
  59fib 0 = 0
  60fib 1 = 1
  61fib n = fib (n - 1) + fib (n - 2)
  62
  63even :: Integer -> Bool
  64even 0 = True
  65even n = odd (n - 1)
  66
  67odd :: Integer -> Bool
  68odd 0 = False
  69odd n = even (n - 1)
  70
  71-- --------------------
  72
  73type Coins = [Int]
  74
  75change :: Int -> Coins -> [Coins]
  76change n cs
  77  | n <  0 = []
  78  | n == 0 = [[]]
  79  | n >  0 = change' cs
  80  where
  81    change' []        = []
  82    change' (c : cs1) = [c : xs | xs <- change (n - c) cs]
  83                        ++
  84                        change n cs1
  85
  86numChanges :: Int -> Coins -> Int
  87numChanges n cs = length (change n cs)
  88
  89change1cent :: [Coins]
  90change1cent = change 1 [50, 20, 10, 5, 2, 1]
  91
  92change2cent :: [Coins]
  93change2cent = change 2 [50, 20, 10, 5, 2, 1]
  94
  95change10cent :: [Coins]
  96change10cent = change 10 [50, 20, 10, 5, 2, 1]
  97
  98change1euro :: Int
  99change1euro = numChanges 100 [50, 20, 10, 5, 2, 1]
 100
 101-- tests
 102
 103test1 :: Int -> Coins -> Bool
 104test1 n cs = all sumEqualsN (change n cs)
 105  where
 106    sumEqualsN xs = sum xs == n
 107
 108test2 :: Int -> Coins -> Bool
 109test2 n cs = all legalCoins (change n cs)
 110  where
 111    legalCoins xs = all (`elem` cs) xs
weiter

Die Quelle

RecFct.hs
SeitenanfangKapitelübersicht
List ComprehensionInhaltsverzeichnisFunktionen höherer Ordnung
Letzte Änderung: 24.11.2020
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel