A function to calculate factorials in math is a common example of recursion.
Linked list and binary tress use recursion
Here is a recursion that prints a message n number of time.
All of these are pretty bad examples of recursion because they can be written with iteration and there is no big loss of clarity or simplicity. Compare and contrast these implementations for examples 1 and 3:
long FactorialUsingRecursion(long n)
if (n < 2) return 1;
return n * FactorialUsingRecursion(n-1);
long FactorialUsingIteration(long n)
long x = 1;
while (n > 1) x *= n--;
void PrintUsingRecursion(std::string const& msg, int howMany)
if (howMany <= 0) return;
std::cout << msg << '\n';
void PrintUsingIteration(std::string const& msg, int howMany)
while (--howMany >= 0) std::cout << msg << '\n';
std::cout << FactorialUsingRecursion(5) << '\n';
std::cout << FactorialUsingIteration(5) << '\n';
Except for binary trees, they are also all linear problems and more prone to stack overflow. Good uses of recursion should have a benefit that outweighs the risk of stack overflow and the overhead of calling the same function over and over. I think quicksort is a better example because the recursive algorithm is much simpler than the iterative one, and with a good pivot finder stack overflow is not as much of a risk.
The biggest problem with giving examples is the best examples solve complex problems and are probably not suited to a beginning programmer, and the examples suited to a student are so weak that he does not learn where and why recursion is a realistic solution.
@ Tom Gunn
You are right that they are bad examples. :)
The only reason I suggested a factorial function is because it was what I did when I first learned about recursion, and Rabex is obviously new to the topic. I also wrote a function involving the fibonacci number sequence.
it was what I did when I first learned about recursion
Yes, me too. Those examples are fine for learning how recursion works, but not for how it can be best used in real code. I think that is what the question was about, and that is why I replied the way I did.
I also wrote a function involving the fibonacci number sequence.
The best thing I learned from a recursive Fibonacci generator is how seemingly innocent code can be criminally inefficient. ;)
Its not supposed to be a good example. Usually, good examples aren't
for beginners. Its supposed to show the concept of recursion,
which is what the OP asked for. I don't think there is a point in
giving a lecture about recursion, and where it could help at this
stage of the OP.
But at the least, the OP should know that most of what recursion can
do, can be done in loops. And most beginner example he will see,
is not worth it. But, still examine the concept, which is what you
are after right now.