Recursion
1. Overview
Recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code.
Most computer programming languages support recursion by allowing a function to call itself from within its own code.
Base Case
A recursive function definition has one or more base cases, meaning inputs for which the function produces a result trivially (without recurring), and one or more recursive case, meaning inputs for which the program recurs (calls itself).
The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. Neglecting to write a base case, or testing for it incorrectly, can cause an infinite loop.