Recursion

Recursion

Photo credit to Giordano Rossoni on Unsplash

Brief description

Recursion is a problem-solving technique that can be used when a problem can be solved by solving one or more, smaller versions of the problem itself, often called divide and conquer.

In practice, it is a meta-function (recursion means self-referencing), i.e. a function that calls itself until the problem is solved.

Build a recursive function

A recursive function needs a base case and a recursive case. The base case is where the function no longer may call itself, while the recursive case is when the function may call itself.

Down below is a function that recursively sums up the first integers until n is called. For each call, the value of n is decremented by one until n equals 0.

#include <iostream>

int sum_n(int n)
{
    if (n == 0) return 0;         /* Base case      */
    else return n + sum_n(n - 1); /* Recursion case */
}

int main()
{
    std::cout << "n = " << 5 << " | sum = " << sum_n(5) << std::endl;
}
user@machine:~$ g++ -g recursion.cpp -o a
user@machine:~/university/sem3/doa/exercises/lecture_6$ ./a
n = 5 | sum = 15

The Stack

To understand recursive functions in programming, some understanding of the stack is required. The stack is a part of the working memory of our computer, therefore it is not suitable for long-term storage. The stack is usually quite small, and stores local variables and some other stuff.

Function calls are also stored on the stack, and they are divided into frames, like a snapshot in time storing the state at that moment. In our program, the call stack would be as follows:

main()
sum_n(5)
 sum_n(4)
  sum_n(3)
   sum_n(2)
    sum_n(1)
     sum_n(0)
     return 0
    return 1 + 0
   return 2 + 1 + 0
  return 3 + 2 + 1 + 0
 return 4 + 3 + 2 + 1 + 0
return 5 + 4 + 3 + 2 + 1 + 0

First, the main function is called, subsequently, the recursive function is called and continues to call itself five times. We are now at the bottom of the stack, time to unwind! As each stack unwinds the value of n in each frame is accumulated, and lastly, returned.

The main box (right) enters the void of meta-function calls, and the sum pops out at the bottom.

Iteration

Recursion is just another way of iterating over a bunch of objects (ints, chars, flowers etc.), therefore this problem is usually solved by using a regular loop.

#include <iostream>

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

int main()
{
    std::cout << "n = " << 5 << " | sum = " << sum_n(5) << std::endl;
}

Recursion also places a bigger load on the system, because of all the calls on the stack, which may lead to stack overflow (see StackOverflow.com). So if it is hard to understand, and crashes the system, then why bother?

Tree Structures, Sorting Algorithms, Graphs, Fractals and other abstract CS terms are all great use cases for recursion

Just stick with loops unless you plan on spending the rest of your career inventing a new tree structure.

Have a good day!