recursion in c

table of contents

hello everyone, in this entry we'll take a look at what recursion is, different types of recursive functions, and we'll do some exercises (with traces included). i hope this is helpful for you!

what is recursion?

in programming, we call a recursive function, a function that calls itself. the following is the general form of a recursive function:

  type
  func (param)
  {
    if (base condition)
      {
        fun (param);
      }
  }

as you can see, there's something called base condition. in a recursive function there must always be a base condition that will determine when the recursion should end, otherwise, it'll keep calling itself indefinitely leading to errors like a stack smash¹.

the following is an example of a recursive function:

  void
  fun1 (int n)
  {
    if (n > 0)
      {
        printf ("%d ", n);
        fun1 (n - 1);
      }
  }

that is a very simple example of a recursive function, it'll just print the parameter that we passed, call itself with n - 1, and keep doing that, as long as n is greater than 0. if we ran that code, we'd get the following output:

  3 2 1

why do we get that output? let's trace that recursive function:

/images/recursion/trace1.jpeg

in that trace, the values that are in the greenish colour is what's printed on the screen. At the end, when we pass fun1 (0) the base condition that checks that n is greater than 0 won't be true, and therefore the code won't be executed.

recursion has two phases: calling phase and returning phase.

calling phase: calling phase is the moment before the recursive call is made, that means, if we have lines of code that are being executed before the recursive call, we say that they are evaluated in calling phase.
returning phase: returning phase are all the statements that are executed after the recursive call, they will be executed after all the recursive calls are finished, that is, when we go back to the function that made the recursive phase. in the following example, we are adding 2 to the result of a recursive call, that means, we are adding 2 at returning phase:
```
  int
  fun1 (int n)
    {
      if (n <= 0)
        return;

      return fun1 (n - 1) + 2;
    }
```

static and global variables in recursion

we can use static and global variables in recursion, if we want them to retain their values through all the recursive calls. let's consider the following function:

  int
  fun (int n)
  {
    static int x = 0;
    if (n > 0)
      {
        x++;
        return fun (n-1) + x;
      }

    return 0;
  }

this would be the tracing for that function:

/images/recursion/trace2.jpeg

as we can see there, for each iteration, we were adding 5 to x at calling time, and as we kept making calls its value increased to 5. if the value x was not static, but global, we'd have obtained the same result.

types of recursion

based in the way a recursive function calls itself, we can label them within different categories, here are the different types of a recursive function:

tail recursion

if the recursive call of a function is the last statement of it, we say that it is of type tail recursion. let's look at an example:

  void
  fun (int n)
  {
    if (n > 0)
      {
        printf ("%d\n", n);
        fun (n - 1);
      }
  }

in that very simple function, as the recursive call is the last statement, we say that it is of type tail recursion. a function is of type tail recursion if everything is made at calling time, and there are no more instructions to be executed at return time. based in that, the following function is not an example of tail recursion:

  fun (n)
  {
    if (n > 0)
      {
        // statement
        // statement
        // statement
        fun (n - 1) + n;
      }
  }

as that function has to add n at returning time, it is not a tail recursive function.

every tail recursive function can be easily transformed into a loop, or vice versa. let's look at an example written as a recursive function, and as a loop side by side:

  void                            | void
  fun (int n)                     | fun (int n)
  {                               | {
    if (n > 0)                    |    while (n > 0)
      {                           |      {
        printf ("%d ", n);        |         printf ("%d ", n);
        fun (n - 1);              |         n--;
      }                           |      }
  }                               | }
  /* Space - O (1) */             | /* Space - O (n) */

if you were to write a tail recursive function, it'd be better to write it as a loop, as recursion is more expensive in terms of space complexity, as it is in the order of n whereas the loop is in the order of 1, so it's constant. that is because for each recursive call, a new activation record must be created in the stack.

head recursion

a head recursive function, is a function whose recursive call is the first statement of the function, basically, it does all its processing after the recursive call, that is, at return time. for example:

  void
  fun (int n)
  {
    if (n > 0)
      {
        fun (n - 1);
        /* statement */
        /* statement */
        /* statement */
        /* statement */
      }
  }

that is a head recursive function.

if a recursive function is neither head or tail recursive, we just call it a recursive function. there's no special name for that.

unlike the tail recursive function, we cannot convert a head recursive function to a loop that easily (before, we could just go through each of the lines of the recursive function, and directly translate them into a loop), for a head recursive function, we need to analyse the problem, and come up with a different solution. for example, let's look at the following code:

  void
  fun (int n)
  {
    if (n > 0)
      {
        fun (n - 1);
        printf ("%d ", n);
      }
  }

we cannot just write a loop like this:

  void
  fun (int n)
  {
    while (n > 0)
      {
        n--;
        printf ("%d ", n);
      }
  }

the output would be completely different.

if we want to have the same output as the head recursive function using a loop, we need to write the code in a different way. it could be written like this:

  void
  fun (int n)
  {
    int i = 1;
    while (i <= n)
      {
        printf ("%d ", i);
        i++;
      }
  }

and with that, we'll get the same output.

tree recursion

if a recursive function is calling itself only once, it is called a linear recursive function, but if it's called more than once, it is called tree recursion. the following is an example of a tree recursive function:

  void
  fun (int n)
  {
    if (n > 0)
      {
        printf ("%d ", n);
        fun (n - 1);
        fun (n - 1);
      }
  }

if we ran fun (3), the output would be the following:

  3 2 1 1 2 1 1

why do we get that output? let's take a look at the trace:

/images/recursion/trace3.jpeg

indirect recursion

in indirect recursion there might be more than one function involved, and they are calling each other in a circular fashion. let's consider these three functions:

                     +-----+
                     |     |
                     |  A  |
                     |     |
                     +-----+
                    /       \            
                   /         \
                  /           \
                 /             \
                /               \
        +------+                 +-----+
        |      |                 |     |
        |  C   +-----------------+  B  |
        |      |                 |     |
        +------+                 +-----+

there we have three functions A, B, and C. in this example, A calls B, B calls C, and C calls A again.

let's look at an actual example:

  void A (int);
  void B (int);

  void
  A (int n)
  {
    if (n > 0)
      {
        printf ("%d\n", n);
        B (n-1);
      }
  }

  void
  B (int n)
  {
    if (n > 1)
      {
        printf ("%d\n", n);
        A (n / 2);
      }
  }

if we execute A (20), we'll get the following output:

  20 19 9 8 4 3 1

let's take a look at the trace, so we know why we are getting that output:

/images/recursion/trace4.jpeg

nested recursion

a nested recursive function, is a function that is recursive, but its argument is a call of itself. for example:

  void
  fun (int n)
  {
    if (< comparison here >)
      {
        /* statement */
        /* statement */
        fun (fun (n - 1));
      }
  }

let's look at an actual function:

  int
  fun (int n)
  {
    if (n > 100)
      return n - 10;
    else
      return fun (fun (n + 11));
  }

if we were to execute fun (95), the output would be 91. let's take a look at why we are getting that output:

/images/recursion/trace5.jpeg

uses of recursion

now let's take a look at some problems that can be solved using recursion.

sum of n natural numbers

let's suppose we have a natural number \(N\), we want to obtain the sum of all the other natural numbers until \(N\). basically, we want to do this: \(1 + 2 + 3 + 4 + \cdots + n - 1 + n\).

the mathematical definition of that problem is the following:

\begin{equation} \text{sum}(n) = \begin{cases} 0, & n = 0 \\ \text{sum}(n - 1) + n, & n > 0 \end{cases} \end{equation}

having a mathematical definition, it's easy for us to write a recursive function using C:

  int
  sum (int n)
  {
    if (n == 0)
      return n;
    return sum (n - 1) + n;
  }

if we run sum (7), the output would be 28.

this can also be implemented as a loop, and as mentioned earlier, it'll be less costly, as recursion is more expensive regarding space complexity:

  int sum = 0;
  for (int i = 0; i <= n; i++)
    {
      sum += i;
    }

however, as we already know, there's already a formula for getting the sum of a natural number, which is the following:

\begin{equation} \text{sum}(n) = \frac{n ( n + 1)}{2} \end{equation}

and this simple formula can be implemented in C like this:

  int sum = (n * (n + 1)) / 2;

this function is so simple i won't do a trace for it.

factorial of a number

obtaining the factorial of a number recursively is a pretty easy task, and really similar to the implementation of the number of n natural numbers. we can define the factorial of a number like this:

\begin{equation} \text{fact}(n) = \begin{cases} 1, & n = 0 \\ \text{fact}(n - 1) \times n, & n > 0 \end{cases} \end{equation}

knowing that, we can implement it recursively in C like this:

  int
  fact (int n)
  {
    if (n == 0)
      return 1;
    return fact (n - 1) * n;
  }

if we ran fact (5) , the output would be 120.

power of a number

we can define the power of a number recursively like this:

\begin{equation} \text{pow}(m, n) = \begin{cases} 1, & n = 0 \\ \text{pow}(m, n - 1) \times m, & n > 0 \end{cases} \end{equation}

we can implement it in C like this:

  int
  pow (int m, int n)
  {
    if (n == 0)
      return 1;
    return pow (m, n - 1) * n;
  }

if we ran pow (2, 9) the output would be 512, and if we ran pow (2, 8) the output would be 256.

however, we can write a faster function, if we do this \(2^8 = (2 \times 2)^4\), we are reducing the number of multiplications by half, that works if we have an even number, if we have an odd number, we can just add another multiplication like this: \(2^9 = 2 \times (2 \times 2)^4\). if can be implemented in C like this:

  int
  pow (int m, int n)
  {
    if (n == 0) return 1;

    if (n % 2 == 0)
      return pow (m * m, n / 2);
    return m * pow (m * m, (n - 1) / 2);
  }

let's take a look at the trace of that new function:

/images/recursion/trace6.jpeg

fibonacci series

we can define the fibonacci series recursively like this:

\begin{equation} \text{fib}(n) = \begin{cases} 0, & n = 0 \\ 1, & n = 1 \\ \text{fib}(n - 2) + \text{fib}(n - 1), & n > 1 \end{cases} \end{equation}

and it can be written in C like this:

  int
  fib (int n)
  {
    if (n <= 1)
      return n;

    return fib (n - 2) + fib (n - 1);
  }

if we want to obtain the 7th term in the fibonacci series, we can run fib (7), and the output would be 13.

we can also write a fibonacci series implementation in C using loops too:

  int
  fib (int n)
  {
    if (n <= 1)
      return n;

    int t0 = 0, t1 = 1, sum = 0;
    for (int i = 2; i <= n; i++)
      {
        sum = t0 + t1;
        t0 = t1;
        t1 = sum;
      }

    return sum;
  }

and as with the previous one, if we were to call fib (7), the result would be 13 as well.

the trace of the recursive implementation is the following:

/images/recursion/trace7.jpeg

if we take a look at the tracing for that function, we can see that it's calling itself several times for fib(3), fib(2), and fib(1) and 0. when a recursive function makes all those repeated calls it's called excessive recursion.

one of the things that we can do avoid all those calls, is to hold the values that we already know in an array. that is called memoization. the new function would look like this:

  int F [10];

  int
  fib (int n)
  {
    if (n <= 1)
      {
        F[n] = n;
        return n;
      }

    if (F[n - 2] == -1)
      F[n - 2] = fib (n - 2);
    if (F[n - 1] == -1)
      F[n - 1] = fib (n - 1);

    return F[n - 2] + F[n - 1];
  }

tower of hanoi

the tower of hanoi problem is the following:

/images/recursion/trace8.jpeg

basically, it consists of moving all the disks from tower A to tower C, using the auxiliary tower B. there are two rules: a big disk cannot go above a smaller disk, and only one disk can be moved at a time.

now, let's try to come up with a recursive solution for this problem.

if we have just one disk, we can move it directly from A to C:

/images/recursion/trace9.jpeg

we move disk from A to C, using B as an auxiliary tower. so we'd call the TOH function like this: TOH (1, A, B, C).

if we have to disks, we move the first disk to B, the big disk to C, and the small disk to B:

/images/recursion/trace10.jpeg

what we are doing now, is that we move the small disk from A to B, using C as auxiliary (TOH (1, A, C, B)), moving disk from A to C, using B as auxiliary (TOH (1, A, B, C)), and finally, moving the disk from B to C, using A as auxiliary (TOH (1, B, A, C)).

if we want to move three disks, we'd need to do this:

/images/recursion/trace11.jpeg

in that step, we are moving n-1 disks recursively, from A to B (basically, repeating all the steps we've done before, it'd be like this: TOH (n - 1, A, C, B)), moving the disk from A to C (TOH (1, A, B, C)), and moving the n-1 disks from B to C (TOH (n - 1, B, A, C)).

knowing that, the recursive implementation to solve this problem would be the following:

  void
  TOH (int n, int A, int B, int C)
  {
    if (n <= 0)
      return;

    TOH (n - 1, A, C, B);
    printf ("from %d to %d\n", A, C);
    TOH (n - 1, B, A, C);
  }

  TOH(3, 1, 2, 3);

if we were to run TOH (3, 1, 2, 3), to move 3 disks from tower 1 to tower 3, the output would be the following:

  from 1 to 3
  from 1 to 2
  from 3 to 2
  from 1 to 3
  from 2 to 1
  from 2 to 3
  from 1 to 3

you can try all those steps here.

conclusion

recursion is really helpful to solve some problems, but we need to know when and how to use it, as it can lead to errors like stack smashing, and sometimes it'll be more resource expensive than using a loop, but overall, it helps us solve some problems easily.

i hope you liked this entry, and that it was helpful for you. i have planned to write about more things like algorithms, data structures, compilers, kernels, and so much more. so… this will be a good foundation before we start diving into all those topics.

⮐ back to blog

Footnotes

stack smash: stack smash is when we try to write outside the function's stack storage space, basically, we ran out of space in the stack. infinite recursion can lead to this, as for each recursive call an activation record is created in the stack, occupying memory.