Recursion
Recursion is the technique of making a function call itself.
This technique provides a way to break complicated problems down into simple problems which are easier to solve.
Recursion may be a bit difficult to understand. The best way to figure out how it works is to experiment with it.
Recursion Example
Adding two numbers together is easy to do, but adding a range of numbers is more complicated.
In the following example, recursion is used to add a range of numbers together by breaking it down into the simple task of adding two numbers:
Example
int sum(int k) {
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}
int main() {
int result = sum(10);
cout << result;
return 0;
}Example Explained
When the sum() function is called, it adds parameter k to the sum of all numbers smaller than k and returns the result. When k becomes 0, the function just returns 0. When running, the program follows these steps:
Since the function does not call itself when k is 0, the program stops there and returns the result.
The developer should be very careful with recursion as it can be quite easy to slip into writing a function which never terminates, or one that uses excess amounts of memory or processor power.
However, when written correctly recursion can be a very efficient and mathematically-elegant approach to programming.
Countdown
This example demonstrates how to use recursion to create a countdown function:
Example
void countdown(int n) {
if (n > 0) {
cout << n
<< " ";
countdown(n - 1);
}
}
int main() {
countdown(5);
}The function calls itself with n - 1 until n becomes 0 .
Factorial of a Number
This example uses a recursive function to calculate the factorial of 5:
Runnable example
int factorial(int n) {
if (n > 1) {
return n * factorial(n - 1);
} else {
return 1;
}
}
int main() {
cout << "Factorial of 5 is " << factorial(5);
return 0;
}Factorial means multiplying a number by every number below it, down to 1 (for example, the factorial of 5 is: 5 * 4 * 3 * 2 * 1 = 120).