O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

1.7  RECURSIVE DEFINITIONS OF FUNCTIONS

We often encounter a definition of a function over the natural numbers such as

f (0, m) = 0

f (n + 1, m) = f (n, m) + m

Is this a legitimate definition? That is, is there really a function that satisfies the above two equalities for all n and m? And if so, is there only one such function, or is the definition ambiguous? We address this question in this section through a somewhat more general related question.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required