Big idea/strategy behind turning while/for loops into recursions? And when is conversion possible/not possible?

Question

I've been writing (unsophisticated) code for a decent while, and I feel like I have a somewhat firm grasp on while and for loops and if/else statements. I should also say that I feel like I understand (at my level, at least) the concept of recursion. That is, I understand how a method keeps calling itself until the parameters of an iteration match a base case in the method, at which point the methods begin to terminate and pass control (along with values) to previous instances and eventually an overall value of the first call is determined. I may not have explained it very well, but I think I understand it, and I can follow/make traces of the structured examples I've seen. But my question is on creating recursive methods in the wild, ie, in unstructured circumstances.

Our professor wants us to write recursively at every opportunity, and has made the (technically inaccurate?) statement that all loops can be replaced with recursion. But, since many times recursive operations are contained within while or for loops, this means, to state the obvious, not every loop can be replaced with recursion. So...

For unstructured/non-classroom situations,

1) how can I recognize that a loop situation can/cannot be turned into a recursion, and

2) what is the overall idea/strategy to use when applying recursion to a situation? I mean, how should I approach the problem? What aspects of the problem will be used as recursive criteria, etc?

Thanks!

Edit 6/29:

While I appreciate the 2 answers, I think maybe the preamble to my question was too long because it seems to be getting all of the attention. What I'm really asking is for someone to share with me, a person who "thinks" in loops, an approach for implementing recursive solutions. (For purposes of the question, please assume I have a sufficient understanding of the solution, but just need to create recursive code.) In other words, to apply a recursive solution, what am I looking for in the problem/solution that I will then use for the recursion? Maybe some very general statements about applying recursion would be helpful too. (note: please, not definitions of recursion, since I think I pretty much understand the definition. It's just the process of applying them I am asking about.) Thanks!

Answer 1

Every loop CAN be turned into recursion fairly easily. (It's also true that every recursion can be turned into loops, but not always easily.)

But, I realize that saying "fairly easily" isn't actually very helpful if you don't see how, so here's the idea:

For this explanation, I'm going to assume a plain vanilla while loop--no nested loops or for loops, no breaking out of the middle of the loop, no returning from the middle of the loop, etc. Those other things can also be handled but would muddy up the explanation.

The plain vanilla while loop might look like this:

1. x = initial value;
2. while (some condition on x) {
3.     do something with x;
4.     x = next value;
5. }
6. final action;

Then the recursive version would be

A. def Recursive(x) {
B.     if (some condition on x) {
C.         do something with x;
D.         Recursive(next value);
E.     }
F.     else { # base case = where the recursion stops
G.         final action;
H.     }
I.
J. Recursive(initial value);

So,

• the initial value of x in line 1 became the orginial argument to Recursive on line J
• the condition of the loop on line 2 became the condition of the if on line B
• the first action inside the loop on line 3 became the first action inside the if on line C
• the next value of x on line 4 became the next argument to Recursive on line D
• the final action on line 6 became the action in the base case on line G

If more than one variable was being updated in the loop, then you would often have a corresponding number of arguments in the recursive function.

Again, this basic recipe can be modified to handle fancier situations than plain vanilla while loops.

Minor comment: In the recursive function, it would be more common to put the base case on the "then" side of the if instead of the "else" side. In that case, you would flip the condition of the if to its opposite. That is, the condition in the while loop tests when to keep going, whereas the condition in the recursive function tests when to stop.

Answer 2

I may not have explained it very well, but I think I understand it, and I can follow/make traces of the structured examples I've seen

That's cool, if I understood your explanation well, then how you think recursion works is correct at first glance.

Our professor wants us to write recursively at every opportunity, and has made the (technically inaccurate?) statement that all loops can be replaced with recursion

That's not inaccurate. That's the truth. And the inverse is also possible: every time a recursive function is used, that can be rewritten using iteration. It may be hard and unintuitive (like traversing a tree), but it's possible.

how can I recognize that a loop can/cannot be turned into a recursion

Simple:

what is the overall idea/strategy to use when doing the conversion?

There's no such thing, unfortunately. And by that I mean that there's no universal or general "work-it-all-out" method, you have to think specifically for considering each case when solving a particular problem. One thing may be helpful, however. When converting from an iterative algorithm to a recursive one, think about patterns. How long and where exactly is the part that keeps repeating itself with a small difference only?

Also, if you ever want to convert a recursive algorithm to an iterative one, think about that the overwhelmingly popular approach for implementing recursion at hardware level is by using a (call) stack. Except when solving trivially convertible algorithms, such as the beloved factorial or Fibonacci functions, you can always think about how it might look in assembler, and create an explicit stack. Dirty, but works.

Answer 3

for(int i = 0; i < 50; i++) 
{
    for(int j = 0; j < 60; j++)
    {
    }
}

Is equal to:

rec1(int i)
{
    if(i < 50)
        return;
    rec2(0);
    rec1(i+1);
}

rec2(int j)
{
    if(j < 60)
        return;
    rec2(j + 1);
}

Every loop can be recursive. Trust your professor, he is right!