An Introduction to Formal Languages and Automata, 7th Edition

13.1 RECURSIVE FUNCTIONS

The concept of a function is fundamental to much of mathematics. As summarized in Section 1.1, a function is a rule that assigns to an element of one set, called the domain of the function, a unique value in another set, called the range of the function. This is very broad and general and immediately raises the question of how we can explicitly represent this association. There are many ways in which functions can be defined. Some of them we use frequently, while others are less common.

We are all familiar with functional notation in which we write expressions like

$$f\left(n\right)=n^2+1.$$

This defines the function f by means of a recipe for its computation: Given any value for the argument n, multiply that value by itself, and then ...