A quick guide to Recursion by example.

What is recursion in programming? It’s not an algorithm, nor a data structure. It’s a way to solve a problem. It’s a way of thinking. It is a process in which a function calls itself directly or indirectly is called recursion, and the corresponding function is called as recursive function.

Recursion is a fairly simple concept. Something that recurs, references itself. The reflection in a mirror of a mirror is recursive: the reflected mirror is reflecting its own image and doing so indefinitely. You’ve also likely seen the Droste effect when using camcorders hooked up to a TV or a computer: when the camcorder is looking at the screen, you can see an infinite series of screens generate themselves, since the camcorder is recording the same image that it’s sending to the screen. The game Portal is a great example of recursion, when two portals could be opened side by side in a narrow space and looking in either one produced an infinite series of the same image.

Example 1: Russian doll

What do Russian dolls have to do with algorithms? Just as one Russian doll has within it a smaller Russian doll, which has an even smaller Russian doll within it, all the way down to a tiny Russian doll that is too small to contain another, we’ll see how to design an algorithm to solve a problem by solving a smaller instance of the same problem, unless the problem is so small that we can just solve it directly. We call this technique recursion.

Example 2: MC Escher’s many drawings.

Escher combined recursion and pattern repetition in a unique way. Some of the works featuring this combination exhibits some complex mathematical and physical ideas, but to the casual viewer the works are sublime. The swans image above features this sort of combination. Note that the swans are tiled very precisely, with the same distance from adjacent swans and swans in the next row. Note also that they are in a closed loop, one construct made possible with recursion.

Example 3: Find Fibonacci numbers with recursion.

Let’s look at the classic Fibonacci sequence algorithm which we are all very familiar with-

function fibonacci(number) {

   if (number < 1)
      return 0

   if (number <= 2)
      return 1

   return fibonacci(number - 1) + fibonacci(number - 2);
}

What’s going on inside?

fib(4) = fib(3) + fib(2) = ( fib(2) + fib(1) ) + ( fib(1) + fib(0))

A real-world example of the above algorithm at work is Phyllotaxis, the beautiful arrangement of leaves, or florets in some plants. The florets in the head of a sunflower form two oppositely directed spirals: 55 of them clockwise and 34 counterclockwise. These numbers are consecutive Fibonacci numbers.

Example 4: Palindrome or Not!

Checking if a string is a palindrome can also be done with recursion.

function isPalindrome(str){
    if(str.length === 0) { 
      return true
    }
    if(str[0] !== str[str.length-1]){
      return false
    }
    return isPalindrome(str.slice(1, str.length-1))
}

console.log(isPalindrome("abccba"))   //true
console.log(isPalindrome("abccdba"))  //false

Example 5: A Fractal Tree!

For this example we’ll need to import p5.js library. In their words-

p5.js is a Javascript library that starts with the original goal of Processing, to make coding accessible for artists, designers, educators, and beginners, and reinterprets this for todays web.

I should clarify that this is not a tutorial on p5 library. It’s a demonstration of a tree drawn recursively with p5.js. Daniel Shiffman of The Processing Foundation and develops tutorials, examples, and libraries for Processing and p5.js. He is also very active on youtube.

So how do we draw a fractal tree. It’s pretty easy actually. The algorithm is as follows-

• We draw the trunk of the tree.
• At the end point of that trunk, we rotate to some degree(in this case 45 degrees) and draw a branch.
• Then we need to comeback to the origin location of the branch, or the end point of the previous branch.
• We rotate and draw the same branch again.

angle = 0;
varslider;
function setup() {
  createCanvas(400, 400);
  slider = createSlider(0, TWO_PI, PI / 4, 0.01);
}
function draw() {
  background(51);
  angle = slider.value();
  stroke(255);
  translate(200, height);
  branch(100);
}
function branch(len) {
  line(0, 0, 0, -len);
  translate(0, -len);
  if (len > 4) {
    push();
    rotate(angle);
    branch(len * 0.67);
    pop();
    push();
    rotate(-angle);
    branch(len * 0.67);
    pop();
  }
}

When everything works out it looks like this -

So what is recursion? A recursion is when something is defined by itself. We all encountered Factorial in math before. That’s a recursive definition. Factorial of 4 is 4 x 3 x 2 x 1. Or, 4! can be defined by 4 x 3!.

That means for any number n, it’s factorial is n x (n-1!).

Two attrebutes of recursion are-

• A function which calls on itself.
• Function will also take in a base case, so that it doesn’t loop infinitely. In the case of factorial of 4, we stop when it gets to 1.

So when is it useful in programming? Not always, yet some extremely efficient algorithms are designed with recursion. Merge sort famously uses recursion for it’s implementation. Many others can be implemented with recursion. Some will take a performance hit, and some can get better. As I have mentioned before, it’s a way of solving problems, not a magic bullet.