Recursion

 

Recursion occurs when a function calls itself. Recursion is useful when dealing with problems that have recursive properties. Consider a function factorial(n) that returns the factorial of n. This function can be defined recursively because factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3) and so on.

Thus, when defining this function you might be tempted to do something like this:

However, this function will not work because the function will keep calling itself forever; it will not know when to stop. Therefore, to define a recursive function, you must define a base case that tells the function when to stop calling itself. In factorial(), you can define a base case to be factorial(0) that returns 1, not further calling factorial(-1).

The above function will now work correctly. Let’s look at how and why factorial() works in detail.

Suppose you call factorial(3). Here is how your computer’s stack will look like:

When you call factorial(3), it returns 3 * factorial(2). factorial(3) waits in the stack while your program calls factorial(2).

factorial(2) returns 2 * factorial(1). Again, your program calls factorial(1) while factorial(2) is waiting in the stack.

factorial(1) returns 1 * factorial(0). Again, your program calls factorial(0), while factorial(1) waits in the stack.

factorial(0) return 1, which is the base case we defined. Now, factorial(1) can be evaluated to be 1. Again, factorial(2) can be now evaluated to be 2 * 1, and so on. Finally, factorial(3) can be evaluated to be 3 * 2, which is 6.