Elimination von Rekursionen

Abstract

Operationen sind in algorithmischen Spezifikationen oft rekursiv beschrieben. Um bei der Implementierung solcher Spezifikationen effiziente Programme zu erhalten, ist es notwendig, Rekursionen in eine repetitive Form zu überführen. Ausgehend von einem Klassifikationsschema für rekursive Funktionen werden zwei Techniken zur Entrekursivierung vorgestellt, die auf der abstrakten Ebene arbeiten. Zunächst werden einige Transformationsschemata von Bauer und Hössner [BaWö 81] übernommen, modifiziert und erweitert, und in einem deterministischen Transformationsregelsystem zusammengefaßt, wobei es wesentlich ist, die Semantik der verwendeten Operationen zu berücksichtigen. Anschließend wird die heuristische unfold/fold-Methode von Darlington und Burstall [DaBu 77] beschrieben und einige ihrer Anwendungsmöglichkeiten dargestellt.

Operations in algorithmic specifications are often described recursively. To obtain efficient programs for implementing such specifications, it is necessary to transform recursive functions into iterative ones. Starting with a Classification scheme for recursive functions, two technics for recursion removal are proposed, which work at abstract levels. At first some transformation schemes from Bauer and Wössner [Bawö 81] are modified, augmented and combined in a rule based transformation system, where it is essential to consider the semantics of the operations used. Subsequently the heuristic unfold/fold method of Darlington and Burstall [DaBu 77] is described and illustrated by examples.