# 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:

1 2 3 4 5 6 7 |
int sum(int final) { int sum = 0; for (int i = 0; i < final; ++i) sum += i; return sum; } |

With recursion, you would write it like this:

1 2 3 4 5 6 7 8 |
int sum(int final, int current) { iff(current == final) return current; return current + sum(final, current + 1); } int total = sum(4, 0); |

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.

1 2 3 4 5 6 7 8 |
int sum(int number) { iff(number == 0) return 0; return number + sum(number-1); } int value = sum(4); |

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).