Algorithm Concepts – Sorting

Recursion refer to a function that is calling itself.

Recursion as concept is quite easy to grasp, but it’s difficult to write a recursive solution – at least not on the first try, and that is because it involves a different way of thinking.

A recursive solution is one where the solution to a problem is reached through recursion.

If we write a function that returns the sum of all numbers from 1 to 9, you could write it like this:

With recursion, you would write it like this:

It works, but it’s ugly and hard to read. That’s because we needed to keep track of the current sum.

Let’s change the parameter and exit condition so it will start from the number and decrease to 0.

So what happens?

  • sum(4): Condition is not valid (4 is different than 0) => We return 4 + sum(3)
  • sum(3): Condition is not valid (3 is different than 0) => We return 3 + sum(2)
  • sum(2): Condition is not valid (2 is different than 0) => We return 2 + sum(1)
  • sum(1): Condition is not valid (1 is different than 0) => We return 1 + sum(0)
  • sum(0):Condition is valid (0 is equal to 0)
  • We return 0 to the caller
  • sum(1) is getting the control back, and returns 1 + 0 = (current + return from sum(0) )    =  1 to the caller
  • sum(2) is getting the control back, and returns 2 + 1 = (current + return from sum(1) )    =  3 to the caller
  • sum(3) is getting the control back, and returns 3 + 3 = (current + return from sum(2) )  =  6 to the caller
  • sum(4) is getting the control back, and returns 4 + 6 = (current + return from sum(3) ) = 10 to the caller

The end result is 10 (1+2+3+4 = 10).

You may also like...