# GAMBAS BOOK 3.15.2

02.07.2018
k10:k10.4:start

## 10.4 Recursion

If you want to give your restless informatics a clear direction and a goal, then you should apply algorithms with a recursive approach to sharply bend your brain in all directions. Recursion is a general procedure for splitting a task step-by-step into elementary solvable subtasks and applying the same algorithm to each subtask. In computer science, the Rekursion is an alternative to the control structure Repetition or Iteration/. The algorithms with a recursive approach are more elegant in their formulation and often shorter, but more difficult to understand in terms of content. This is also illustrated by the two mathematical examples presented, which first describe the mathematical task, then derive an inductively formulated function and finally present the algorithm for calculating the function values.

## 10.4.1 Calculation of the sum of natural numbers

The calculation of the sum of natural numbers from 1 to i can be used as a function sum (i) = 1+2+….Define +i inductive like this:

• total (0) = 0 sum (i) = i + sum (i - 1) for i > 0

Calculation of the function values of sum (i):

```PUBLIC FUNCTION summe(i AS Integer) AS Integer
IF i = 0 THEN
RETURN 0
ELSE
RETURN i + summe(k - 1) ' Recursive call with reduced argument!
ENDIF
END ' summe(..) ```

## 10.4.2 Calculation of a product of natural numbers

The calculation of the product of the natural numbers from 1 to k as a product (k) = 1 * 2 * 3 *… * k designates k-faculty and describes it with the symbol k! The function faculty (k) can thus be defined inductively:

• faculty (0) = 1 and faculty (1) = 1
• faculty (k) = k * faculty (k-1) for k > 1

Calculation of the functional values of faculty (k):

```PUBLIC FUNCTION fakultaet(k AS Integer) AS Integer
IF k = 0 OR k = 1 THEN
RETURN 1
ELSE
RETURN k * fakultaet(k - 1) ' Recursive call with reduced argument!
ENDIF
END```

## 10.4.3 Evaluation of rational terms

The task is quite simple: Calculation of the value of an expression with the following Input alphabet = {0.. 9, +, -, *, /, comma} taking into account the priority or ranking of the operations. The solution is based on the recursive descent method and provides, for example, for the expression 2,88+5*6,7-8/4/ as a value the rational number 34,38:

Figure 10.4.3.1: Evaluation for an expression

The complete source code is specified in the following section. Please note that the input characters of the entered expression are not checked and no error handling is built in to keep the source code as simple and legible as possible.

Source code:

```' Gambas class file

PUBLIC SUB Form_Open()
FMain.Center
FMain.Border = 1
txtTerm.SetFocus
END

PUBLIC SUB btnInfoAnzeigen_Click()
Balloon.Info("Input alphabet:" & Chr(10) & "0..9, + , - , * , / , Komma", LAST)
END

PUBLIC SUB txtTerm_Change()
txtWert.Clear
END

PUBLIC FUNCTION anfang(zeichenkette AS String, zeichen AS String) AS String
DIM position, anzahl AS Integer
position = InStr(zeichenkette, zeichen)
anzahl = position - 1
RETURN Mid\$(zeichenkette, 1, anzahl)
END

PUBLIC FUNCTION copyab(zeichenkette AS String, i AS Integer) AS String
DIM anzahl AS Integer
anzahl = Len(zeichenkette) - i + 1
RETURN Mid\$(zeichenkette, i, anzahl)
END

PUBLIC FUNCTION ende(zeichenkette AS String, zeichen AS String) AS String
DIM position, anzahl AS Integer
position = InStr(zeichenkette, zeichen)
anzahl = position + 1
RETURN copyab(zeichenkette, anzahl)
END

PUBLIC FUNCTION TermToReell(s AS String) AS Float
IF InStr(s, "+") > 0 THEN
RETURN TermToReell(anfang(s, "+")) + TermToReell(ende(s, "+"))
ELSE IF InStr(s, "-") > 0 THEN
RETURN TermToReell(anfang(s, "-")) - TermToReell(ende(s, "-"))
ELSE IF InStr(s, "/") > 0 THEN
RETURN TermToReell(anfang(s, "/")) / TermToReell(ende(s, "/"))
ELSE IF InStr(s, "*") > 0 THEN
RETURN TermToReell(anfang(s, "*")) * TermToReell(ende(s, "*"))
ELSE
RETURN Val(s)
ENDIF
END

PUBLIC SUB btnTermAuswerten_Click()
txtWert.Text = Str(TermToReell(txtTerm.Text))
END ```

The TermToReell(expression) function, which is recursively called with constantly changing arguments, carries the main burden of calculating the value of the expression entered. For the simple expression 1+2*3-4/5, see how the value 6.2 has been calculated. To do this, it is also necessary to deal with the 3 functions used for processing character strings in order to find out what these functions do.

The algorithms presented belong to a subproject for a function parser, with which it was possible to calculate function values for a given f function. The complete project can be found in the download area together with the projects Term0 - from which the source code above originates - and Term0E. The Term0E project contains a character scanner and necessary error handling procedures.

The advantage of the developed and tested function saver is the definition of special functions such as faculty(k), which for example are not present in the component gb. eval.

Figure 10.4.3.2: Calculation of a value table with displayed help (foldable)

Articles and Projects

## ﻿10.4 Rekursion

Wenn Sie Ihrem rastlosen informatischen Tun eine klare Richtung und ein Ziel geben wollen, dann sollten Sie sich Algorithmen mit einem rekursiven Ansatz zuwenden, um Ihr Gehirn in alle Richtungen heftig zu verbiegen. Die Rekursion ist ein allgemeines Verfahren, um eine Aufgabe schrittweise in elementar lösbare Teilaufgaben zu zerlegen und auf jede Teilaufgabe den gleichen Algorithmus anzuwenden. In der Informatik ist die Rekursion eine Alternative zur Kontrollstruktur Wiederholung oder Iteration. Die Algorithmen mit rekursivem Ansatz sind zwar eleganter in der Formulierung und oft kürzer, aber schwerer inhaltlich zu verstehen. Das wird auch an den zwei vorgestellten Beispielen aus der Mathematik deutlich, bei denen zuerst die mathematische Aufgabe beschrieben wird, dann eine induktiv formulierte Funktion abgeleitet wird und abschließend der Algorithmus zur Berechnung der Funktionswerte vorgestellt wird.

## 10.4.1 Berechnung der Summe natürlicher Zahlen

Die Berechnung der Summe natürlicher Zahlen von 1 bis i lässt sich als Funktion summe(i) = 1+2+…+i induktiv so definieren:

• summe(0) = 0
• summe(i) = i + summe(i - 1) für i > 0

Berechnung der Funktionswerte von summe(i):

```PUBLIC FUNCTION summe(i AS Integer) AS Integer
IF i = 0 THEN
RETURN 0
ELSE
RETURN i + summe(k - 1) ' Rekursiver Aufruf mit reduziertem Argument!
ENDIF
END ' summe(..) ```

## 10.4.2 Berechnung eines Produktes natürlicher Zahlen

Die Berechnung des Produktes der natürlichen Zahlen von 1 bis k als produkt(k) = 1 * 2 * 3 * … * k nennt k-Fakultät und beschreibt es mit dem Symbol k! . Die Funktion fakultät(k) kann so induktiv definiert werden:

• fakultät(0) = 1 und fakultät(1) = 1
• fakultät(k) = k * fakultät(k-1) für k > 1

Berechnung der Funktionswerte von fakultät(k):

```PUBLIC FUNCTION fakultaet(k AS Integer) AS Integer
IF k = 0 OR k = 1 THEN
RETURN 1
ELSE
RETURN k * fakultaet(k - 1) ' Rekursiver Aufruf mit reduziertem Argument!
ENDIF
END ' fakultaet(..) ```

## 10.4.3 Auswertung rationaler Terme

Die Aufgabe ist recht einfach: Berechnung des Wertes eines Ausdrucks mit folgendem Eingabe-Alphabet = {0..9, + , - , * , / , Komma} unter der Beachtung der Wertigkeit oder Rangfolge der Operationen. Die Lösung basiert auf der Methode des rekursiven Abstiegs und liefert zum Beispiel für den Ausdruck 2,88+5*6,7-8/4 als Wert die rationale Zahl 34,38:

Abbildung 10.4.3.1: Auswertung für einen Ausdruck

Es wird im folgenden Abschnitt der vollständige Quelltext angegeben. Bitte beachten Sie, dass keine Überprüfung der Eingabezeichen des eingegeben Ausdrucks erfolgt und auch keine Fehlerbehandlung eingebaut ist, um den Quelltext so einfach wie möglich und gut lesbar zu halten.

Quelltext:

```' Gambas class file

PUBLIC SUB Form_Open()
FMain.Center
FMain.Border = 1
txtTerm.SetFocus
END

PUBLIC SUB btnInfoAnzeigen_Click()
Balloon.Info("Eingabe-Alphabet:" & Chr(10) & "0..9, + , - , * , / , Komma", LAST)
END

PUBLIC SUB txtTerm_Change()
txtWert.Clear
END

PUBLIC FUNCTION anfang(zeichenkette AS String, zeichen AS String) AS String
DIM position, anzahl AS Integer
position = InStr(zeichenkette, zeichen)
anzahl = position - 1
RETURN Mid\$(zeichenkette, 1, anzahl)
END

PUBLIC FUNCTION copyab(zeichenkette AS String, i AS Integer) AS String
DIM anzahl AS Integer
anzahl = Len(zeichenkette) - i + 1
RETURN Mid\$(zeichenkette, i, anzahl)
END

PUBLIC FUNCTION ende(zeichenkette AS String, zeichen AS String) AS String
DIM position, anzahl AS Integer
position = InStr(zeichenkette, zeichen)
anzahl = position + 1
RETURN copyab(zeichenkette, anzahl)
END

PUBLIC FUNCTION TermToReell(s AS String) AS Float
IF InStr(s, "+") > 0 THEN
RETURN TermToReell(anfang(s, "+")) + TermToReell(ende(s, "+"))
ELSE IF InStr(s, "-") > 0 THEN
RETURN TermToReell(anfang(s, "-")) - TermToReell(ende(s, "-"))
ELSE IF InStr(s, "/") > 0 THEN
RETURN TermToReell(anfang(s, "/")) / TermToReell(ende(s, "/"))
ELSE IF InStr(s, "*") > 0 THEN
RETURN TermToReell(anfang(s, "*")) * TermToReell(ende(s, "*"))
ELSE
RETURN Val(s)
ENDIF
END

PUBLIC SUB btnTermAuswerten_Click()
txtWert.Text = Str(TermToReell(txtTerm.Text))
END ```

Die Hauptlast der Berechnung des Wertes des eingegebenen Ausdrucks trägt die Funktion TermToReell(ausdruck), die mit ständig wechselnden Argumenten rekursiv aufgerufen wird. Erkunden Sie für den einfachen Ausdruck 1+2*3-4/5, wie der Wert 6,2 berechnet worden ist. Dazu ist es notwendig, sich auch mit den verwendeten 3 Funktionen zur Bearbeitung von Zeichenketten zu befassen, um zu ergründen was diese Funktionen leisten.

Die vorgestellten Algorithmen gehören zu einem Teilprojekt für einen Funktionsparser, mit dem Funktionswerte für eine vorgegebene Funktion f berechnet werden konnten. Das vollständige Projekt finden Sie im Download-Bereich zusammen mit den Projekten Term0 – aus dem der o.a. Quelltext stammt – und Term0E. Das Projekt Term0E enthält einen Zeichen-Scanner und notwendige Fehlerbehandlungsprozeduren.

Als Vorteil des entwickelten und getesteten Funktionsparsers kann die Definition von speziellen Funktionen wie fakultät(k) genannt werden, die zum Beispiel in der Komponente gb.eval nicht vorhanden sind.

Abbildung 10.4.3.2: Berechnung einer Wertetabelle mit angezeigter Hilfe (ausklappbar)