recursion

[Rabex]

can s/o plz give a simple example of how recursion can be used in programming....im new to this topic so i need help i cant develop new codes myself.

[Grn Xtrm]

A function to calculate factorials in math is a common example of recursion. The function calls itself until it reaches its "base case", which in the factorial example is n=0.

[gerard4143]

Linked list and binary tress use recursion

[mrnutty]

Here is a recursion that prints a message n number of time. Its not been
tested.

void PrintUsingRecursion(string msg, int howMany)
{  
     if(howMany <= 0) return; //BASE CASE
    
      cout<<msg<<endl;
      PrintUsingRecusion(msg,howMany-1);
    
}

[Tom Gunn]

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:

#include <iostream>
#include <string>

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--;

    return x;
}

void PrintUsingRecursion(std::string const& msg, int howMany)
{  
    if (howMany <= 0) return;

    std::cout << msg << '\n';

    PrintUsingRecursion(msg, howMany-1);   
}

void PrintUsingIteration(std::string const& msg, int howMany)
{
    while (--howMany >= 0) std::cout << msg << '\n';
}

int main()
{
    std::cout << FactorialUsingRecursion(5) << '\n';
    std::cout << FactorialUsingIteration(5) << '\n';

    PrintUsingRecursion("recursion", 5);
    PrintUsingIteration("iteration", 5);
}

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.

[Grn Xtrm]

@ 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.

[Tom Gunn]

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. ;)

[mrnutty]

All of these are pretty bad examples of recursion

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.

[Tom Gunn]

Its supposed to show the concept of recursion,
which is what the OP asked for.

Then we will have to disagree until the OP clarifies his question. I think he was asking for realistic uses of recursion, not contrived ones.

[mrnutty]

Then we will have to disagree until the OP clarifies his question. I think he was asking for realistic uses of recursion, not contrived ones.

Agreed. To me, OP's question, seems to say one thing, and then
another.