Recursion Basics

1Introduction

This lecture explains a recursive algorithm as a method that constructs the result for an input from the result for a smaller input of the same kind. It defines the base case, recursive step, and termination measure needed for the design, and proves termination and correctness separately. It also explains the execution process through the call stack and analyzes its complexity.

2Components of a Recursive Algorithm

A recursive algorithmRecursive algorithm is an algorithm that applies itself to another input during a computation. Such an application is a recursive callRecursive call.

A base caseBase case is a condition under which the algorithm returns a result directly without making a recursive call. A recursive stepRecursive step transforms an input that does not satisfy a base case into a smaller input of the same kind and constructs the original result from the result of the recursive call.

A termination measureTermination measure assigns a nonnegative integer to every input and strictly decreases in every recursive call. It is used to prove that recursive calls cannot continue indefinitely.

3Recursive Definition of Factorial

For $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0}, factorial is defined by

The specification of $$\mathrm{fact}\left(n\right)$$\operatorname{fact}(n) is: given $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0}, return $$n!$$n!. A recursive algorithm satisfying this specification is

fact(n):
    if n = 0:
        return 1
    return n * fact(n - 1)

The condition $$n=0$$n=0 is the base case, and the computation of $$n\mathrm{fact}(n-1)$$n\operatorname{fact}(n-1) for $$n\ge 1$$n\geq1 is the recursive step. We choose $$\mu \left(n\right)=n$$\mu(n)=n as the termination measure.

4Termination

If $$n=0$$n=0, the algorithm terminates without a recursive call. If $$n\ge 1$$n\geq1, the recursive call receives $$n-1$$n-1, and

Thus, the nonnegative-integer termination measure strictly decreases in every recursive call. A strictly decreasing sequence of nonnegative integers cannot be infinite, so the computation reaches $$n=0$$n=0 after finitely many calls. Therefore, $$\mathrm{fact}\left(n\right)$$\operatorname{fact}(n) terminates for every $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0}.

5Correctness

Termination guarantees that the computation ends, but it does not by itself guarantee that the return value satisfies the specification. We prove the latter claim by induction on $$n$$n.

• Base case: for $$n=0$$n=0, the algorithm returns $$1$$1. Since $$0!=1$$0!=1, the return value is correct.
• Inductive step: let $$n\ge 1$$n\geq1 and assume $$\mathrm{fact}(n-1)=(n-1)!$$\operatorname{fact}(n-1)=(n-1)!. The algorithm returns $$n\mathrm{fact}(n-1)$$n\operatorname{fact}(n-1). By the inductive hypothesis and the definition of factorial,

Therefore, $$\mathrm{fact}\left(n\right)=n!$$\operatorname{fact}(n)=n! for every $$n\in Z_{\ge 0}$$n\in\mathbb{Z}_{\geq0}. The base case and recursive step correspond respectively to the base case and inductive step of the proof.

6Call Stack

A stack frameStack frame is a record containing the arguments, local variables, return location, and other information required by one function call. The call stackCall stack stores the stack frames of unfinished calls in last-in, first-out order.

During the evaluation of $$\mathrm{fact}\left(3\right)$$\operatorname{fact}(3), frames for $$\mathrm{fact}\left(3\right)$$\operatorname{fact}(3), $$\mathrm{fact}\left(2\right)$$\operatorname{fact}(2), $$\mathrm{fact}\left(1\right)$$\operatorname{fact}(1), and $$\mathrm{fact}\left(0\right)$$\operatorname{fact}(0) are pushed in that order. After the base case returns $$1$$1, the calls return in reverse order and construct $$1$$1, $$2$$2, and $$6$$6. Consequently, the recursive-call depth determines the number of frames stored simultaneously.

7Complexity

We use the unit-cost RAM modelUnit-cost RAM model, in which every arithmetic operation costs $$\mathrm{\Theta }\left(1\right)$$\Theta(1), and count arithmetic operations. An analysis of arbitrary-precision bit complexity must instead account for the number of bits in $$n!$$n! and the cost of the multiplication algorithm.

In this model, for each input with $$n>0$$n>0, $$\mathrm{fact}\left(n\right)$$\operatorname{fact}(n) makes one recursive call and performs a constant-time multiplication. Its time complexity satisfies

so $$T\left(n\right)=\mathrm{\Theta }\left(n\right)$$T(n)=\Theta(n). The maximum call depth is $$n+1$$n+1. Because each frame uses a constant amount of storage, the auxiliary-space complexity of the call stack is $$\mathrm{\Theta }\left(n\right)$$\Theta(n).

8Design and Verification Procedure

1. State the specification of the input and return value.
2. Define a base case that requires no recursive call.
3. Define a recursive step that constructs the result from a smaller input of the same kind.
4. Provide a termination measure that strictly decreases in every recursive call, and prove termination.
5. Prove correctness, for example by induction.
6. Evaluate time and space complexity from the number of recursive calls and the maximum call depth.