What is recursion and why is it useful?

Recursion is when a named block of code (a subroutine or function) calls itself. We can use recursion to describe some algorithms in very few lines. For example, the following block of pseudocode will recursively print out the numbers less than 10 in the Fibonacci sequence:
function fibonacci (int n, int m, int max) { int sum = n+m; if (sum <= max) { print (sum); fibonacci (m, sum, max); } } fibonacci (0, 1, 10);
This algorithm is recursive because inside the fibonacci function we can see a call to the fibonacci function. This will itself call the fibonacci function and so on until one of these calls fails the check in the if statement and runs to the end of the function instead. In all cases where recursion is a viable solution, a loop will also do the job (try to rewrite the above code with a while loop instead!). Often loops are better as they don't hog resources (e.g. memory) like recursion tends to do. So why would you ever use recursion? Sometimes (in very simple programming languages) we do not have loops and so recursion is the only way to loop code at all, but sometimes recursive code is just easier to read and understand than the equivalent loop. Writing code that is easy to understand is one of the most important things to think about when programming (second only to making sure your code is actually working!).