Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 70
Beispiel 3.4 Rekursive Funktionsdefinition
ОглавлениеEin Beispiel für eine Rekursion zeigt folgende Definition:
| f(x, y) | = | if x = 0 then y else ( |
| if x > 0 then f(x − 1, y) + 1 else −f (−x, −y) fi) fi |
Die bisherige Auswertungsstrategie kann auf rekursive Funktionsdefinitionen ebenfalls angewandt werden, so dass wir folgende Auswertungen erhalten:
| f(0, y) | y für alle y | |
| f (1, y) | f (0, y) + 1 y + 1 | |
| f(2, y) | f (1, y) + 1 (y + 1) + 1 y + 2 | |
| … | ||
| f(n, y) | y + n für alle n ∊ int, n > 0 | |
| f(−1, y) | −f (1, −y) −(1− y) y − 1 | |
| … | ||
| f(x, y) | x + y für alle x, y ∊ int |
Unsere rekursive Definition realisiert also die Addition nur mithilfe der Successor-Funktion »+1«.
