Writing recursive algorithms

From the introduction you may have noticed that in order to write recursive algorithms we need to follow these rules:

So "thinking recursively" (btw this is the name of a very good book!) implies not thinking of the solution to a problem as a whole but rather to think of a base case and what can I do to get closer to it!

Not all problems are recursive. We can think of recursion as a subset of divide and conquer, since we are dividing the original problem in smaller ones but here the important thing to note is that this subproblems must be of exactly the same shape as the original one and therefore we can apply the original solution to the subproblems! This is, we can recurse!

Previously I mentioned that the idea of recursion comes from math, for example, you can find lots of math functions defined recursively like factorial function, also mathematical induction is recursion. The curious thing to note here is that in mathematical induction we start from the base case the general one but when programming we start from the general to the base!