Is a while loop intrinsically a recursion?

Question

I wondered whether a while loop is intrinsically a recursion?

I think it is because a while loop can be seen as a function that calls itself at the end. If it is not recursion, then what is the difference?

Answer 1

Loops are very much not recursion. In fact, they are the prime example of the opposite mechanism: iteration.

The point of recursion is that one element of processing calls another instance of itself. The loop control machinery merely jumps back to the point where it started.

Jumping around in code and calling another block of code are different operations. For instance, when you jump to the start of the loop, the loop control variable still has the same value it had before the jump. But if you call another instance of the routine you're in, then the new instance has new, unrelated copies of all of its variables. Effectively, one variable can have one value on the first level of processing and another value on a lower level.

This capability is crucial for many recursive algorithms to work, and this is why you can't emulate recursion via iteration without also managing a stack of called frames which keeps track of all those values.

Answer 2

This depends on your point of view.

If you look at computability theory, then iteration and recursion are equally expressive. What this means is that you can write a function that computes something, and it doesn't matter whether you do it recursively or iteratively, you will be able to choose both approaches. There is nothing you can compute recursively which you can not compute iteratively and vice versa (although internal workings of the program might be different).

Many programming languages don't treat recursion and iteration the same, and for good reason. Usually, recursion means that the language/compiler handles the call stack, and iteration means you might have to do stack-handling yourself.

However, there are languages -- especially functional languages -- in which things like loops (for, while) are indeed only syntactic sugar for recursion and implemented behind the scenes that way. This is often desirable in functional languages, because they usually don't have the concept of looping otherwise, and adding it would make their calculus more complex, for little practical reason.

So no, they are not intrinsically the same. They are equally expressive, meaning you can not compute something iteratively you can't compute recursively and vice versa, but that's about it, in the general case (according to the Church-Turing thesis).

Note that we are talking about recursive programs here. There are other forms of recursion, e.g. in data structures (e.g. trees).

---

If you look at it from an implementation point of view, then recursion and iteration are pretty much not the same. Recursion creates a new stack frame for every call. Every step of the recursion is self-contained, getting the arguments for the computation from the callee (itself).

Loops on the other hand don't create call frames. For them, the context is not preserved on each step. For the loop, the program merely jumps back to the start of the loop until the loop condition fails.

This is quite important to know, since it can make pretty radical differences in the real world. For recursion, the whole context has to be saved on every call. For iteration, you have precise control about what variables are in memory and what is saved where.

If you look at it that way, you quickly see that for most languages, iteration and recursion are fundamentally different and have different properties. Depending on the situation, some of the properties are more desirable then others.

Recursion can make programs more simple and easier to test and proof. Converting a recursion to iteration usually makes the code more complex, increasing the likelihood for failure. On the other hand, converting to iteration and reducing the amount of call stack frames can save much needed memory.

Answer 3

Saying that X is intrinsically Y only makes sense if you've got some (formal) system in mind that you are expressing X in. If you define the semantics of while in terms of the lambda calculus, you might mention recursion*; if you define it in terms of a register machine, you probably won't.

In either case, people probably won't understand you if you call a function recursive just because it contains a while loop.

* Though perhaps only indirectly, for example if you define it in terms of fold.

Answer 4

The difference is the implicit stack and semantic.

A while loop that "calls itself at the end" has no stack to crawl back up when it's done. It's last iteration sets what state will be as it ends.

Recursion however can't be done without this implicit stack that remembers the state of work done before.

It is true that you can solve any recursion problem with iteration if you give it access to a stack explicitly. But doing it that way is not the same.

The semantic difference has to do with the fact that looking at recursive code conveys an idea in a completely different way than iterative code. Iterative code does things a step at a time. It accepts whatever state that came from before and only works to create the next state.

Recursive code breaks a problem into fractals. This little part looks like that big part so we can do just this bit of it and that bit of it the same way. It's a different way to think about problems. It's very powerful and takes getting used to. A lot can be said in a few lines. You just can't get that out of a while loop even if it has access to a stack.

Answer 5

It all hinges on your use of the term intrinsically. On the programming language level, they are syntactically and semantically different, and they have quite different performance and memory use. But if you dig deep enough into theory they can be defined in terms of each other, and is therefore "the same" in some theoretical sense.

The real question is: When does it makes sense to distinguish between iteration (loops) and recursion, and when is it useful to think of it as the same things? The answer is that when actually programming (as opposed to writing mathematical proofs) it is important to distinguish between iteration and recursion.

Recursion creates a new stack frame, i.e. a new set of local variables for each call. This has overhead, and takes up space on the stack, which means that a deep enough recursion may overflow the stack which causes the program to crash. Iteration on the other hand only modifies the existing variables so is generally faster and only takes up a constant amount of memory. So this is a very important distinction for a developer!

In languages with tail-call recursion (typically functional languages), the compiler may be able to optimize recursive calls in such a way that they only takes up a constant amount of memory. In those languages the important distinction is not iteration vs recursion, but non-tail-call-recursion version tail-call-recursion and iteration.

Bottom line: You need to be able to tell the difference, otherwise your program will crash.

Answer 6

while loops are a form of recursion, see e.g. the accepted answer to this question. They correspond to the μ-operator in computability theory (see e.g. here).

All variations of for loops that iterate on a range of numbers, a finite collection, an array, and so on, correspond to primitive recursion, see e.g. here and here. Note that the for loops of C, C++, Java, and so on, are actually syntactic sugar for a while loop, and therefore it does not correspond to primitive recursion. The Pascal for loop is an example of primitive recursion.

An important difference is that primitive recursion always terminates, whereas generalized recursion (while loops) may not terminate.

EDIT

Some clarifications regarding comments and other answers. "Recursion occurs when a thing is defined in terms of itself or of its type." (see wikipedia). So,

Is a while loop intrinsically a recursion?

Since you can define a while loop in terms of itself

while p do c := if p then (c; while p do c))

then, yes, a while loop is a form of recursion. Recursive functions are another form of recursion (another example of recursive definition). Lists and trees are other forms of recursion.

Another question that is implicitly assumed by many answers and comments is

Are while loops and recursive functions equivalent?

The answer to this question is no: A while loop corresponds to a tail-recursive function, where variables that are accessed by the loop correspond to the arguments of the implicit recursive function, but, as others have pointed out, non-tail-recursive functions cannot be modeled by a while loop without using an extra stack.

So, the fact that "a while loop is a form of recursion" does not contradict the fact that "some recursive functions cannot be expressed by a while loop".

Answer 7

A tail call (or tail recursive call) is exactly implemented as a "goto with arguments" (without pushing any additional call frame on the call stack) and in some functional languages (Ocaml notably) is the usual way of looping.

So a while loop (in languages having them) can be seen as ending with a tail call to its body (or its head test).

Likewise, ordinary (non tail-call) recursive calls can be simulated by loops (using some stack).

Read also about continuations and continuation-passing style.

So "recursion" and "iteration" are profoundly equivalent.

Answer 8

It is true that both recursion and unbounded while-loops are equivalent in terms of computational expressiveness. That is, any program written recursively can be rewritten into an equivalent program using loops instead, and vice versa. Both approaches are turing-complete, that is either can be used to compute any computable function.

The fundamental difference in terms of programming is that recursion allows you to make use of data that gets stored on the call stack. To illustrate this, assume you want to print a elements of a singly-linked list using either a loop or recursion. I'll use C for the example code:

 typedef struct List List;
 struct List
 {
     List* next;
     int element;
 };

 void print_list_loop(List* l)
 {
     List* it = l;
     while(it != NULL)
     {
          printf("Element: %d\n", it->element);
          it = it->next;
     }
 }

 void print_list_rec(List* l)
 {
      if(l == NULL) return;
      printf("Element: %d\n", l->element);
      print_list_rec(l->next);
 }

Simple, right? Now let's make one slight modification: Print the list in the reverse order.

For the recursive variant, this is an almost trivial modification to the original function:

void print_list_reverse_rec(List* l)
{
    if (l == NULL) return;
    print_list_reverse_rec(l->next);
    printf("Element: %d\n", l->element);
}

For the loop function though, we have a problem. Our list is singly-linked and thus can only be traversed forward. But since we are printing in reverse, we have to start printing the last element. Once we reached the last element, we cannot go back to the second-to-last element anymore.

So we either have to do a whole lot of re-traversing, or we have to build an auxiliary data structure that keeps track of the visited elements and from which we can then print efficiently.

Why don't we have this problem with recursion? Because in recursion we already have an auxiliary data structure in place: The function call stack.

Since recursion allows us to return to the previous invocation of the recursive call, with all local variables and state for that call still intact, we gain some flexibility that would be tedious to model in the iterative case.

Answer 9

Loops are a special form of recursion to achieve a specific task (mostly iteration). One can implement a loop in a recursive style with the same performance [1] in several languages. and in the SICP [2], you can see for loops are described as "syntastic sugar". In most imperative programming languages, for and while blocks are using the same scope as their parent function. Nonetheless, in most of the functional programming languages there is neither for nor while loops exist because there is no need for them.

The reason imperative languages have for/while loops is that they are handling states by mutating them. But actually, if you look from different perspective, if you think of a while block as a function itself, taking parameter, process it, and return a new state - which could as well be the call of the same function with different parameters - you can think of loop as a recursion.

The world could also be defined as mutable or immutable. if we define the world as a set of rules, and call an ultimate function that takes all the rules, and the current state as parameters, and return the new state according to these parameters which has the same functionality (generate next state in the same way), we could as well say that is a recursion and a loop.

in the following example, life is the function takes two parameters "rules" and "state", and new state will be constructed in the next time tick.

life rules state = life rules new_state
    where new_state = construct_state_in_time rules state

[1]: tail call optimization is a common optimization in functional programming languages to use the existing function stack in recursive calls instead of creating a new one.

[2]: Structure and Interpretation of Computer Programs, MIT. https://mitpress.mit.edu/books/structure-and-interpretation-computer-programs

Answer 10

A while loop is different than recursion.

When a function is called, the following takes place:

1. A stack frame is added to the stack.

2. The code pointer moves to the beginning of the function.

When a while loop is at the end the following occurs:

1. A condition asks if something is true.

2. If so, the code jumps to a point.

In general, the while loop is akin to the following pseudocode:

 if (x)

 {

      Jump_to(y);

 }

Most important of all, recursion and loops have different assembly code representations, and machine code representations. This means that they are not the same. They may have the same results, but the different machine code proves they are not 100% the same thing.

Answer 11

Just iteration is insufficient to be generally equivalent to recursion, but iteration with a stack is generally equivalent. Any recursive function can be reprogrammed as an iterative loop with a stack, and vice-versa. This does not mean that it is practical, however, and in any particular situation one or the other form may have clear benefits over the other version.

I'm not sure why this is controversial. Recursion and iteration with a stack are the same computational process. They are the same "phenomenon", so to speak.

The only thing I can think of is that when looking at these as "programming tools", I would agree that you should not think of them as the same thing. They are "mathematically" or "computationally" equivalent (again iteration with a stack, not iteration in general), but that doesn't mean you should approach problems with the thought that either one will do. From an implementation/problem-solving point of view, some problems may work better one way or the other, and your job as a programmer is to decide correctly which one is better suited.

To clarify, the answer to the question Is a while loop intrinsically a recursion? is a definite no, or at least "not unless you have stack as well".