Page 152 - ARM 64 Bit Assembly Language

138 Chapter 5

are based upon recursive rules. For example, the formal definition of the natural numbers by
the Peano axioms can be formulated as:
1. 0 is a natural number, and
2. each natural number has a successor, which is also a natural number.

Using one base case and one recursive rule, it is possible to generate the set of all natural
numbers. Other recursively defined mathematical objects include functions and sets.

Listing 5.30 shows the C code for a small program which uses recursion to reverse the order
of characters in a string. The base case where recursion ends is when there are less than two
characters remaining to be swapped. The recursive rule is that the reverse of a string can be
created by swapping the first and last characters and then reversing the string between them.
In short, a string is reversed if:

1. the string has a length of zero or one character, or
2. the first and last characters have been swapped and the remaining characters have been
reversed.

In Listing 5.30, line 6 checks for the base case. If the string has not been reversed according to
the first rule, then the second rule is applied. Lines 8–10 swap the first and last characters, and
line 11 recursively reverses the characters between them.

Listing 5.30 A C program that uses recursion to reverse a string.

1 #include <stdio.h>
2 #include <string.h>
3
4 void reverse(char *a, int left, int right)
5 {
6 if(left < right)
7 {
8 char tmp = a[left];
9 a[left] = a[right];
10 a[right] = tmp;
11 reverse(a, left+1, right-1);
12 }
13 }
14
15 int main()
16 {
17 char str[] = "\nThis is the string to reverse\n";
18 printf(str);
19 reverse(str, 0, strlen(str)-1);
20 printf(str);
21 return 0;
22 }