18: Recursion
- Page ID
- 54227
The Google search result for recursion, shows Recursion, did you mean recursion?
Recursion is a powerful general-purpose programming technique and is used for some important applications including search and sorting methods. Recursion is the idea that a function may call itself (which is the basis for the joke).
Recursion can be very confusing in its simplicity and power. The examples in this section will not be enough in themselves for the reader to obtain recursive enlightenment. The goal of this section is to provide an introduction to the concept on recursion. The simple examples here, which are used introduce recursion, are meant to help demonstrate the form and structure for recursion. More complex examples (than will be discussed here) should be studied and implemented in order to ensure a complete appreciation for the power of recursion.
The calling process previously described supports recursion without any changes. A recursive routine must have a recursive definition that includes:
- base case, or cases, that provide a simple result (that defines when the recursion should stop).
- rule, or set of rules, that reduce toward the base case.
This recursive definition is referred to as a recursive relation.
- 18.1: Recursive Subroutines
- A recursive subroutine declaration must be preceded by the keyword recursive.
- 18.2: Recursive Print Binary Example
- This section provides an example recursive subroutine to accept a decimal number and print that number in binary.
- 18.3: Recursive Functions
- A recursive function declaration must be preceded by the keyword recursive. In addition, the keyword result must be explicitly added to the function declaration.
- 18.4: Recursive Factorial Example
- This section provides an example recursive function to compute the mathematical factorial function.
- 18.5: Recursive Factorial Function Call Tree
- In order to better understand recursion, a recursion tree can help show how the recursive calls interact.