Recursive definition

is defined by the rules This definition is valid for each natural number n, because the recursion eventually reaches the base case of 0.

The definition may also be thought of as giving a procedure for computing the value of the function n!, starting from n = 0 and proceeding onwards with n = 1, 2, 3 etc.

Most recursive definitions have two foundations: a base case (basis) and an inductive clause.

[3] Where the domain of the function is the natural numbers, sufficient conditions for the definition to be valid are that the value of f(0) (i.e., base case) is given, and that for n > 0, an algorithm is given for determining f(n) in terms of n,

The formal criteria for what constitutes a valid recursive definition are more complex for the general case.

However, a specific case (domain is restricted to the positive integers instead of any well-ordered set) of the general recursive definition will be given below.

The even numbers can be defined as consisting of The notion of a well-formed formula (wff) in propositional logic is defined recursively as the smallest set satisfying the three rules: The definition can be used to determine whether any particular string of symbols is a wff: Logic programs can be understood as sets of recursive definitions.

The logic programming language Prolog uses backward reasoning to solve goals and answer queries.

Four stages in the construction of a Koch snowflake . As with many other fractals , the stages are obtained via a recursive definition.