Recursion

This chapter covers notes on recursion.

  1. Recursion Theorem
  2. Natural Summation
  3. Factorial

Recursion Theorem

Recursion is a mathematical theorem implied by the construction of the natural numbers. Recall that the theorem's statement:

recursion theorem. Let S{\Ss} be a set with x∈S{x \in \Ss} and the injective function f:S⇀S.{f : \Ss \inj \Ss.} Then there exists a function g:Nβ†’X{g : \nat \to X} such that

(1) g(0)=x,{g(0) = x,} and

(2) βˆ€n∈N[g(n+1)=f(g(n))].{\forall n \in \nat [g(n + 1) = f(g(n))].}

Because computers operate, fundamentally, with the natural numbers N,{\nat,} there is a close relationship between the recursion theorem and programming. Many problems have some form of self-similarity or self-reference. Put differently, the problem can be solved by using facts from a previous attempt at the problem to make the problem smaller or simpler. Whenever we encounter such problems, our best bet is to try recursion.

For recursion to work, we must define the "simpler" boundary β€” where the problem can't get any simpler. This is called the base case. It follows that before we reach the base case, we might have to go through many versions of the problem. These are versions of the problem larger than the base case, but smaller than the original problem. Some of these problem versions are called recursive cases β€” versions of the problem that allow us to get to a simpler case. Others are non-recursive cases β€” versions of the problem where the road ends; we know there isn't a solution and should stop trying.

In the materials that follow, we explore the relationship between the recursion theorem and programming. To do so, much of the materials are examples of recursive data structures and algorithms, rather than pure theory.

Natural Summation

Arguably, the simplest example of recursion is computer the natural summation of n{n} β€” the sum of the natural numbers up to n.{n.} For example, the sum of (0,1)=0+1=1.{\ar{0,1} = 0 + 1 = 1.} The sum of (0,1,2,3)=0+1+2+3=6.{\ar{0,1,2,3} = 0+1+2+3 = 6.} We can use an iterative algorithm for this sum:

natsumi(n):N↣N.{\df{natsum}_i(n) : \nat \bij \nat.}

Let n∈N.{n \in \nat.} Then the function natsumi{\df{natsum}_i} returns the result of the series βˆ‘i=0ni{\dsum{i=0}{n} i} iteratively.

  1. variablesΒ sum←0{\vars \let{sum}{0}} , i←1{\let{i}{1}}
  2. while i<n{i \lt n} do:
    1. sum:=sum+i{sum := sum + i}
    2. i:=i+1{i := i + 1}
    3. goto line[2]{\line{2}}
  3. return sum{sum}

Now the recursive approach:

natsumr(n):N↣N.{\df{natsum}_r(n) : \nat \bij \nat.}

Let n∈N.{n \in \nat.} Then the function natsumr{\df{natsum}_r} returns the result of the series βˆ‘i=0ni{\dsum{i=0}{n} i} recursively.

  1. ifΒ n=0{\if n = 0} β‡’{\nc} return 0{0}
  2. elseΒ {\else} return natsumr(nβˆ’1)+n{\df{natsum}_r(n-1) + n}

The recursive approach is much shorter. Indeed, for many problems, a recursive implementation proves to be far more elegant than an iterative implementation.

Factorial