Recipe: How To Translate A Recursive Function Into An Implicite One

by on October 18, 2021

In order to determine the runtime of a recursive function, it is helpful to translate this function into an implicite one. This blog post illustrates a straight-forward approach, intuitively – with exactly 5 steps on a small example. This approach is also applicable for almost every recursive function.

Why Tho?

The reason to resolve a recursive function lies in the analysis and application. When interested in runtime analysis, the implicite function will serve as a guidance for the total runtime of the recursive function. When interested in application, the implicite function will have the same

results for the same input, but mostly with way less calculation overhead. Transferring a recursion might be a burden, but is effective nonetheless.

An Overview Of The Recipe

First, I want to give you guys an overview of the five steps I mentioned:

  1. Find a general pattern of behaviour.
  2. Specify the recursive function in the i-th step and prove its correctness.
  3. “Find” the end of the recursion, substitute at the i-th step and calculate the result.
  4. ???
  5. Profit.

With these steps, we will be able to overcome this big burden.

The Example

For our transition today, consider this small, cozy example:

(1)   \begin{align*}&T(n) = 2^{n-1} + T(n-1)\\&T(0) = 0\end{align*}


Small and cozy? Yes. Because I state that the result can be “seen” with a practiced eye almost instantly. We will start with the first step – what is the general pattern? How does this recursion “behave”?

1. The general pattern

We are interested in the behaviour of the recursive scheme. So, lets unfold it and see, what happens:

(2)   \begin{align*}T(n) &= 2^{n-1} + T(n-1)\\&= 2^{n-1} + 2^{(n-1)-1} + T((n-1)-1)\\&= 2^{n-1} + 2^{n-2} + 2^{n-3} + T(n-3)\\&= 2^{n-1} + 2^{n-2} + 2^{n-3} + … + 2^{n-i} + T(n-i)\\T(n)_i &= \sum_{k = 1}^{i} 2^{n-k} + T(n-i)&&\text{the $i$-th step!}\end{align*}

2. Specify the recursive function in the i-th step and prove the correctness

In the last equation, we recognize a general pattern for the recursion in the i-th step. Lets check, whether its valid:

(3)   \begin{align*}T(n)_i = &\sum_{k=1}^{i} 2^{n-k} + T(n-i)\\T(n)_1 = &\sum_{k=1}^{1} 2^{n-k} + T(n-1) = 2^{n-1} + T(n-1)\\T(n)_2 = &\sum_{k=1}^{2} 2^{n-k} + T(n-2) = 2^{n-1}+2^{n-2} + T(n-2)\end{align*}

Hm, looks fine to me. But unfortunately, this is not a formal proof of correctness! I just wanted to validate if this makes any sense. Now, we are all set to proof its correctness formally. How? With the tool of mathematical induction (Vollständige Induktion) over i.

Let’ summarize the mathematical induction (vollständige Induktion) again. For convenience, at first in english, then in german.

Mathematical Induction In English

  1. Base case: This is the point of validation for one value of i, generally valued in where we want the statement begin to hold with increasing i. For the small, cozy example, the base case is i = 1.
  2. Induction hypothesis: Here, we assume the validity for the statement for i.
  3. Induction step: Here, we prove the correctness in the i+1-th step, using the hypothesis in a suiting equation.

Vollständige Induktion auf Deutsch

  1. Induktionsanfang: Der IA ist dafür da, um wenigstens eine Gültigkeit zu sehen. Werte einsetzen, bestens, wo die Induktion anfängt, in unserem Fall i = 1 (ein Rekursionschritt). Haben wir oben schon gesehen, passt.
  2. Induktionsvoraussetzung: Die IV beinhaltet die Annahme, dass die Aussage stimmt für ein gewissen Index. Nennen wir den Index mal i. ‘Bis dahin’ sei die Aussage richtig. Dies schreibt ihr kurz in einem Satz hin, dass das gilt.
  3. Induktionschritt: Unter der Tatsache, dass die Aussage stimmt für i, ist zu zeigen, dass sie auch richtig ist für den Nachfolger der Zahl. Wir schauen uns T(n)i an, verwenden irgendwie die IV und wollen dann aufs richtige Ergebnis kommen.

The proof

  1. Base case:
    For the base case, we evaluate i = 1. We get:

        \begin{align*}T(n)_1 = &\sum_{k=1}^{1} 2^{n-k} + T(n-1) = 2^{n-1} +T(n-1) ~~~~~ \checkmark\end{align*}

  2. Induction hypothesis:
    It is assumed that the statement holds for i. We now have to prove that it will also hold for i+1.
  3. Induction step:

    (4)   \begin{align*}T(n)_i = \sum_{k=1}^{i} 2^{n-k} + T(n-i)\end{align*}


    The hypothesis states that this is correct. Now, we apply one more recursion unfolding / unrolling and will see, that it still holds.

    (5)   \begin{align*}T(n)_i =&\sum_{k=1}^{i} 2^{n-k} + T(n-i)\\\underbrace{\Rightarrow}_{\text{unfolding}} &\sum_{k=1}^{i} 2^{n-k} + 2^{n-i-1}+T(n-i-1)\\=&\sum_{k=1}^{i} 2^{n-k} + 2^{n-(i+1)}+T(n-(i+1))\\=&\sum_{k=1}^{i+1}2^{n-k} + T(n-(i+1)) \underline{\underline{= T(n)_{i+1}}}\end{align*}

Great! We now have proven, that the statement follows for i+1, assuming, that its correct for i and then by the domino effect, it is proven for all i\geq1!

3. Find the end of the recursion, substitute and get the implicite function

If we start at n and decrement by 1 in every recursion, then, the depth of recursion values n. Quite simple, right?

(6)   \begin{align*}T(n)_n = \sum_{k=1}^n 2^{n-k} + \underbrace{T(0)}_{=0}\end{align*}


Now, finalize the result! Use the geometric sum to get the following expression:

(7)   \begin{align*}T(n)_n = \sum_{k=0}^{n-1} 2^k= 2^{n}-1\end{align*}

Now, we got the implicite form of T(n) and know in analysis, that the recursion is in fact an exponential function. The calculation takes place in \mathcal{O}(1) instead of \mathcal{O}(n).

4. ???

If the reader were in a situation, in which this task was to be fulfilled in some sort of exam, then this kind of recipe will surely bring some success. Then, the last step also holds:

5. Profit.

How could we have “seen” the implicite result in the recursion itself? We somehow sum up 2 to the power of k, where k traverses from n to 1. This is how binary calculation works. This is the bit representation:

(8)   \begin{align*} T(n) = \underbrace{111..111}_{n-1\text{ times}} = 2^n - 1 \end{align*}

Thanks for reading and as always, stay safe 🙂

Author

  • Benjamin Coban

    Hi there, Benjamin here! Interested in theoretical computer science, DevOps and being a tiny gem of musical expression with caffine addiction, I try to reach the public with posts about theory, applications and their interaction. Feel free to stop by and start a discussion! 🙂

    View all posts