What is recursion?
Simply put, a recursive function is a function that calls itself. In practice, this means that the following function is an example of a recursive function:
func recursive() {
recursive()
}
In this example, if the user would call the function “recursive,” all it would do would call itself ad infinitum. Effectively, this is an infinite loop and not the most useful function. To make recursive functions useful, we can extend our definition of a recursive function a bit further by setting up two rules:
- A function must have a condition on which to call itself (recurse)
- A function must have a condition on which it returns without calling itself
The first condition just states that given a function, X, at some point in the function’s body, X will be called again. The second condition is that there exists a case for which the function, X, returns from the function without calling itself. This second condition...