In the particular case of the factorial function, you'll run into the limits of your number type way before you hit the buffer overflow.
To complement what Washu said, recursive functions are sometimes more clear than iterative ones, and they are also easy to
memoize, leading to a very readable implementation of dynamic programming for some problems.
For instance, the following C++ program computes how many ways you can make 1 dollar (100 cents) using coins of 1 cent, 5 cents, 10 cents, 25 cents, 50 cents and 1 dollar.
#include <iostream>
int coin_types[] = {1,5,10,25,50,100};
int make_change(int n, int max_coin_type) {
if (max_coin_type == 0)
return 1; // only 1 way to make any number of cents if you only use 1-cent coins
int result = 0;
for (; n >= 0; n-=coin_types[max_coin_type])
result += make_change(n, max_coin_type-1);
return result;
}
int main() {
std::cout << make_change(100,5) << '\n';
}
This algorithm is pretty clean (I think), but it takes time O(n^k), k being the number of coin types (6). If we use some memory to remember past results, the algorithm becomes dynamic programming, with a much better performance of O(k*n). So, for instance, you can compute how many ways you can make change of 20 dollars using those same coins denominations:
#include <iostream>
int coin_types[] = {1,5,10,25,50,100};
int make_change(int n, int max_coin_type) {
int const memory_size = 2001;
static int memory[6][memory_size] = {0};
if (max_coin_type == 0)
return 1; // only 1 way to make any number of cents if you only use 1-cent coins
if (n < memory_size && memory[max_coin_type][n] > 0)
return memory[max_coin_type][n]; // I remember this one!
int result = 0;
for (; n >= 0; n-=coin_types[max_coin_type])
result += make_change(n, max_coin_type-1);
if (n < memory_size)
memory[max_coin_type][n] = result; // let's remember the result
return result;
}
int main() {
std::cout << make_change(2000,5) << '\n';
}
Of course, this can be implemented without recursion, but I think the code would be less readable. There are other algorithms that are even less amenable to being written without recursion. The best example of this is alphabeta search, which is used for the AI in games like chess.
0
