Introduction to Programming Languages

Background and Fundamental Concepts ◾ 45

2.2.3 Recursion

Recursion means that the denition uses itself in the denition, although with a smaller

data set or argument value. Recursion can be used to dene a recursive function, such as

factorial or Fibonacci, or a recursive data structure, such as linked list or trees.

A recursive denition has at least one base case and at least one recursive denition. e

recursive denition progressively unfolds and approaches the base case(s). In a nite num-

ber of unfoldings, the recursion is terminated by the base case, and the result of the compu-

tation is passed back in the reverse order to the calling invocation of the recursive function.

e number of invocations of recursive functions is decided ...