When to use recursion?

Question Detail: 

When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?

Asked By : Taylor Huston

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1418

Answered By : Juho

I have taught C++ to undergraduates for about two years and covered recursion. From my experience, your question and feelings are very common. At an extreme, some students see recursion as difficult to understand while others want to use it for pretty much everything.

I think Dave sums it up well: use it where it is appropriate. That is, use it when it feels natural. When you face a problem where it fits nicely, you will most likely recognize it: it will seem like you cannot even come up with a iterative solution. Also, clarity is an important aspect of programming. Other people (and you also!) should be able to read and understand the code you produce. I think it is safe to say iterative loops are easier to understand at first sight than recursion.

I don't know how well you know programming or computer science in general, but I strongly feel that it does not make sense to talk about virtual functions, inheritance or about any advanced concepts here. I have often started with the classic example of computing Fibonacci numbers. It fits here nicely, since Fibonacci numbers are defined recursively. This is easy to understand and does not require any fancy features of the language. After the students have gained some basic understanding of recursion, we have taken another look at some simple functions we have built earlier. Here's an example:

Does a string contain a character $x$?

This is how we did it before: iterate the string, and see if any index contains $x$.

bool find(const std::string& s, char x) {    for(int i = 0; i < s.size(); ++i)    {       if(s[i] == x)          return true;    }     return false; } 

The question is then, can we do it recursively? Sure we can, here's one way:

bool find(const std::string& s, int idx, char x) {    if(idx == s.size())       return false;     return s[idx] == x || find(s, ++idx); } 

The next natural question is then, should we do it like this? Probably not. Why? It's harder to understand and it's harder to come up with. Hence it is more prone to error, too.