Recursive Functions and Recurrences

Iterative Functions

We can introduce iteration with constructs like for and while with conditionals (if).

int x = 10;
int y = 20;
while (x < y) {
    printf("%d\n", x);
    x++;
}

Here, the loop keeps running until the condition x < y becomes false. This ensures the program halts.

If we change the loop so that the condition never becomes false:

while (1) {
    printf("%d", x);
}

then the program runs indefinitely (non-terminating).

Recursive Functions

A recursive function is a function that calls itself.

For example, consider the recurrence:

\[T(n) = T(n-1) + f(n)\]

This means “to compute $T(n)$, we first compute $T(n-1)$, then add some extra work $f(n)$.”

A recursive function must have a base case so that it eventually stops calling itself.

Example, define:

\[N(k) = N(k-1)\]

and do not specify a base case. If we call $N(4)$, then:

\[N(4) = N(3) = N(2) = N(1) = N(0) = N(-1) = \dots\]

This never halts, because no base case exists.

So let’s define the base case at:

\[N(1) = 1\]

Now, if we compute $N(4)$:

\[\begin{align*} N(4) &= N(3) \\ &= N(2) \\ &= N(1) \\ &= 1 \end{align*}\]

The recursion terminates and produces a value. The important idea is that the base case has no recursive call.

🤓☝️ Recursive Functions in the Language of Iteration We can think of iteration and recursion as two flavors of “repeated work.”

  • An iterative function repeats a subroutine using loops.
  • A recursive function repeats itself with a smaller or modified input.

If we don’t introduce conditionals in iterative functions, they may run indefinitely.
If we don’t introduce a base case in recursive functions, they also run indefinitely.

The factorial function is a well-known recursive function. Since we may define it recursively as

  • Base case: $0! = 1$
  • Recursive Function: $N! = N(N-1)!$

Another one is the formula for calculating the $n$-th Fibonacci number.

  • Base cases: $F_0 = 0; F_1 = 1$
  • Recursive Function: $F_n = F_{n-1} + F_{n-2}$

Notice for the Fibonacci number we have two base cases and two recursive calls.

Recurrences

We describe the running time of an iterative function through summations which we then simplify to a closed-form solution.

On the other hand, for recursive functions, we describe its running time through a recurrence relation and solving this recurrence relation we get a closed-form of the recursive function.

Looking at the implementation of the recursive Fibonacci function in fibonacci.c.

We have two base cases which are both constant time $\mathcal{O}(1)$ and the recursive case has two recursive calls $\texttt{fibo_rec}(n-1)$ and $\texttt{fibo_rec}(n-2)$. Hence, we can define $\texttt{fibo_rec}(n)$ as the function

\[T(n) = \begin{cases} a, & n = 0 \vee n = 1 \\ T(n-1) + T(n-2) + b, & n > 1 \end{cases}\]

❓ Where did $a$ and $b$ come from? These are variables that represent “extra work” in the algorithm that comes with each recursive call. So, there just there to “abstract” the “other non-recursive stuff” in our function.

❓ What is $T(n)$? Again, $T(n)$ serves as an abstraction for a recursive function. In this case, $T(n)$ is just a nickname or synonym for $\texttt{fibo_rec}(n)$.

Now looking at the implementation of the recursive Factorial function in factorial.c.

We have a single base case which is constant time $\mathcal O(1)$ and the recursive call $\texttt{fact_rec}(n-1)$. Therefore,

\[T(n) = \begin{cases} a, & n = 1 \\ T(n-1) + b, & n > 1 \end{cases}\]

Closed-Form Expressions

An expression is in closed-form is what we formally call our “usual” idea of a mathematical expression. It is composed of at least one of the following:

  • Constants
  • Variables
  • Standard functions
  • Function compositions of standard functions

Examples:

  • Quadratic Formula: $\frac{-b\pm\sqrt{b^2-4ac}}{2a}$
  • Sum/Difference Identity for $\tan(\theta \pm \phi)$: $\frac{\tan\theta \pm \tan\phi}{1 \mp \tan\theta\tan\phi}$
  • Formula for the Golden Ratio: $\frac{1+\sqrt 5}{2}$

Solving Recurrences by Iteration

Step 1. First take note of the base case of the recurrence and pick an approriate recursive case1. Step 2. Expand each recursive case until we reach the base case. Step 3. Transform to summation and simplify to get the closed-form.

Example, define:

\[\begin{align*} \text{Recursive case: } & T(n) = T(n-2) - T(n-1), \\ & n > 5 \\ \text{Base case: } & T(3) = 9 \\ & T(4) = 16 \end{align*}\]

Step 1, choose approriate enough recursive case. Choose $T(7)$. Step 2, expand $T(7)$ using definition above

\[\begin{align*} T(7) &= T(5) - T(6) \end{align*}\]

Recursively expand until we reach $T(3)$ or $T(4)$.

\[\begin{align*} T(7) &= (T(3) - T(4)) - T(6) \\ &= -7 - (T(4) - T(5)) \\ &= -7 - (16 - (T(3) - T(4))) \\ &= -7 - (16 + 7) \\ &= -30 \end{align*}\]

Notice that on the next iteration each non-base case recursive calls will “split” into two. For instance, look at $T(6)$, at the next iteration $T(6)$ splits into $T(4)-T(5)$. Luckily $T(4)$ is a base case, but $T(5)$ isn’t and further splits into two $T(3),T(4)$.

Hence, for a large enough $p$ in the domain of $T$.

\[\begin{align*} T(p) &= \underline{T(p-2)} - T(p-1) \\ &= \underline{(T(p-4) - T(p-3))} - (T(P-3) - T(p-2)) \\ &= \underline{((T(p-6) - T(p-5)) - (T(p-5) - T(p-4)))} \dots \end{align*}\]

Notice that the underline part grows by a factor of $2^n$ after each iteration $\left(2^0, 2^1, 2^2, \dots\right)$. Therefore, the time complexity of the recursive function is $\mathcal O(2^n)$.

Problems Set for Recursive Functions and Recurrences

For 1-8. Refer to the C code below:

int procedure(int* arr, int i, int l, int h)
{
    int j = l - (h + l) / 2

    if ( arr[j] == i)
        return 1
    if ( arr[j] > i )
        return procedure(arr, i, l, j--)
    if ( arr[j] < i )
        return procedure(arr, i, j++, h)
}
  1. What is the base case?
  2. How many recursive cases are there? What does each recursive case do?
  3. What is the iterative equivalent of procedure?
    1. This function is also known as?
  4. What is the recurrence of procedure?
  5. What is the closed form of procedure?
  6. What is the time complexity of procedure?
  7. What is the space complexity of procedure?

  8. Compare the time and space complexity of the recursive function and its iterative equivalent.

  9. Given a tree (T = (V, E)), where each vertex (v \in V), it has a corresponding value $\overline v\in \mathbb Z$. The tree satisfies that for every vertex (v) with children (x) and (y): \(\overline{x} < \overline{v} < \overline{y}\) Write a recursive function that takes the tree $T$ and a vertex $k\in V$ that returns the two children of $k$.

AI Use Declaration. See AI Use Declaration

  1. Obviously, we don’t want a long solution. So, pick a low enough recursive case that is close to the base case that would still allow for us to notice a pattern! ↩