C++Recursion
Recursion
Recursion is the technique of making a function call itself.
This technique provides a wayto break complicated problems down into simple problems which are easier to solve.
Recursion may be a bit difficult to understand. Thebest 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 morecomplicated.
In the following example, recursion is used to add a range of numberstogether by breaking it down into the simple task of adding two numbers:
Example
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}
int main() {
int result = sum(10);
cout << result;
return 0;
}
Example Explained
When thesum() function is called, it adds parameterk to the sum of all numbers smallerthank and returns the result. When k becomes 0, the function just returns 0. Whenrunning, the program follows these steps:
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
Since the function does not call itself whenk is 0, the program stops there and returns theresult.
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.
Factorial of a Number
This example uses a recursive function to calculate the factorial of 5:
using namespace std;
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).
