37

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?

  • 1
  • 13
    You can convert recursion to iteration and vice versa, yes. That doesn't mean they are the same, they just have the same capabilities. There are times when recursion is more natural, and there are times where iteration is more natural. – Polygnome Jul 24 '16 at 13:36
  • 18
    @MooingDuck You can prove by induction that any recursion can be written as iteration and vice versa. Yes, it will look very different, but you can do it nonetheless. – Polygnome Jul 24 '16 at 18:17
  • 6
    What does intrinsically same mean here? In programming, using recursion means a specific thing, which is different from iteration (loops). In CS, when you get closer to the theoretical maths side of things, these things start to mean a bit different things. – hyde Jul 25 '16 at 7:19
  • 3
    @MooingDuck The conversion from recursive to iterative is actually pretty trivial. You just keep a stack of function-call parameters and a stack of resultsfor the function calls. You replace the recursive calls by adding the parameters to the call stack. sure there's all the handling of the stack that breaks a bit the structure of the algorithm, but once you understand this is quite easy to see that the code does the same thing. Basically you are explicitly writing the call stack that is implicit in the recursive definitions. – Bakuriu Jul 25 '16 at 17:50

11 Answers 11

117

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.

  • 10
    @Giorgio That may be true, but it's a comment on a claim the answer didn't make. "Arbitrarily" is not present in this answer and would significantly changes the meaning. – hvd Jul 24 '16 at 11:43
  • 12
    @hvd In principle, tail recursion is full recursion like any other. Intelligent compilers can optimize away the actual "creating a new stack frame" part so that the generated code is very similar to a loop, but the concepts we're talking about apply to the source code level. I consider the form an algorithm has as source code the important thing, so I'd still call it recursion – Kilian Foth Jul 24 '16 at 15:56
  • 15
    @Giorgio "this is exactly what recursion does: call itself with new arguments" — except for the call. And the arguments. – hobbs Jul 24 '16 at 18:34
  • 12
    @Giorgio You are using diffferent definitions of words than most here. Words, you know, are the basis of communication. This is Programmers, not CS Stack Exchange. If we used words like "argument", "call", "function" etc the way you suggest, it would be impossible to discuss about actual code. – hyde Jul 25 '16 at 9:29
  • 6
    @Giorgio I am looking at the abstract concept. There's the concept where you recur and the concept where you loop. They're different concepts. Hobbs is 100% correct that there are no arguments and there is no call. They are fundamentally and abstractly different. And that's good because they solve different problems. You, on the other hand, are looking at how you might implement loops when your only tool is recursion. Ironic you're telling Hobbs to stop thinking about implementation and start looking at concepts when your methodology is the one that really needs the reassessment. – corsiKa Jul 25 '16 at 15:13
37

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.

  • 4
    To be fair, the function isn't recursive in any definition. It just contains an recursive element, the loop. – Luaan Jul 25 '16 at 10:04
  • @Luaan: Definitely so, but since in languages with a while construct recursivity is generally a property of functions, I just can't think of anything else to describe as "recursive" in this context. – Anton Golov Jul 26 '16 at 17:43
36

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.

  • A language with local variables and recursion but no arrays could perform tasks which could not be performed by an iterative language with local variables and no arrays. For example, report whether an input contains an alphanumeric string of unknown length followed by a blank and then the characters of the original string in reverse order. – supercat Jul 25 '16 at 15:29
  • 3
    As long as the language is turing complete, it can. An array can easily be replaced by a (doubly) linked list, for example. Talking about iteration or recursion and wether they are equal only makes sense if you compare two turing-complete languages. – Polygnome Jul 25 '16 at 15:33
  • I meant having nothing other than simple static or automatic variables, i.e. not being Turing-complete. A purely-iterative language would be limited to those tasks that can be accomplished via simple deterministic finite automaton, while a recursive language would add the ability to perform tasks that would require at least a pushdown deterministic finite automaton. – supercat Jul 25 '16 at 16:01
  • 1
    If the language isn't turing complete, its pointless to begin with. DFAs can neither do arbitrary iteration nor recursion btw. – Polygnome Jul 25 '16 at 16:17
  • 2
    No implementation is actually Turing-complete, and languages which are not Turing-complete can be useful for many purposes. Any program that can be run with a a finite number of variables with a finite range can be accommodated by a DFA where every possible combination of values is a discrete state. – supercat Jul 25 '16 at 16:45
12

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.

  • 5
    I think "implicit stack" is misleading. Recursion is part of a language's semantics, not an implementation detail. (Granted, most recursion-supporting languages use a call stack; but firstly, a few such languages don't, and secondly, even in languages that do, not every recursive call necessarily appends to the call stack, since many languages support optimizations such as tail call elimination.) Understanding the usual/simple implementation can be useful in getting a handle on the abstraction, but you shouldn't trick yourself into thinking it's the whole story. – ruakh Jul 25 '16 at 2:45
  • 2
    @ruakh I would argue a function that executes in constant space by using tail call elimination really is a loop. Here the stack isn't the implementation detail, it's the abstraction that allows you to accumulate different states for different levels of recursion. – Cimbali Jul 25 '16 at 12:05
  • @ruakh: any state within a single recursive call will be stored on an implicit stack, unless the recursion can be converted by the compiler into a iterative loop. The tail call elimination is an implementation detail, the one which you need to be aware of if you want to reorganize your function to be tail-recursive. Also, "few such languages don't" - can you provide an example of languages which don't need a stack for recursive calls? – Groo Jul 26 '16 at 11:10
  • 1
    @Groo: See en.wikipedia.org/wiki/Continuation-passing_style. – ruakh Jul 26 '16 at 14:20
  • @ruakh: CPS by itself creates the same implicit stack, so it must rely on tail call elimination to make sense (which it makes trivial due to way it's constructed). Even the wikipedia article you linked to says the same: Using CPS without tail call optimization (TCO) will cause not only the constructed continuation to potentially grow during recursion, but also the call stack. – Groo Jul 26 '16 at 15:42
7

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.

3

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

  • 2
    @morbidCode: primitive recursion and μ-recursion are forms of recursion with specific restrictions (or lack thereof), studied e.g. in computability theory. As it turns out, a language with just a FOR loop can compute exactly all primitive recursive functions, and a language with just a WHILE loop can compute exactly all µ-recursive functions (and it turns out that the µ-recursive functions are exactly those functions that a Turing Machine can compute). Or, to make it short: primitive recursion and µ-recursion are technical terms from maths / computability theory. – Jörg W Mittag Jul 24 '16 at 11:49
  • 2
    I thought "recursion" implied a function calling itself, resulting in the current execution state being pushed to the stack and so on; therefore most machines have a practical limit on how many levels you can recurse. While loops don't have any such limits because they internally would use something like a "JMP" and don't use the stack. Just my understanding, could be wrong. – Jay Jul 24 '16 at 13:53
  • 13
    This answer is using a completely different definition for the word "recursive" than the OP was using, and is thus highly misleading. – Mooing Duck Jul 24 '16 at 18:05
  • 2
    @DavidGrinberg: Quoting: "the C, C++, Java for loops are not an example of primitive recursion. Primitive recursion means that the maximum number of iterations / recursion depth is fixed before starting the loop." Giorgio is talking about Computability theory primitives. Unrelated to programming languages. – Mooing Duck Jul 24 '16 at 18:08
  • 3
    I have to agree with Mooing Duck. While computability theory might be interesting in theoretical CS, I think everyone agrees that the OP was talking about the programming languages concept. – Voo Jul 24 '16 at 19:30
2

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.

1

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.

  • 1
    Of course, the second recursive function is not tail-recursive - it's a lot harder to optimise for space as you can't use TCO to reuse the stack. Implementing a doubly linked list would make both algorithms trivial either way, at the cost of the space of a pointer/reference per element. – Baldrickk Jul 25 '16 at 15:40
  • @Baldrickk The funny thing about tail-recursion is that you end up with a version that is much closer to what the loop version would have looked like, as it again removes your ability to store state on the call stack. A doubly linked list would solve it, but redesigning the data structure is often not an option when running into this problem. While the example here is somewhat artificially constrained, it illustrates a pattern that pops up frequently in functional languages in the context of recursive algebraic types. – ComicSansMS Jul 25 '16 at 20:28
  • My point was that if you run into this problem, it's more down to a lack of functional design, than which language constructs you use to implement it, and each choice has its own positives and negatives :) – Baldrickk Jul 26 '16 at 12:21
0

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

  • 4
    @Giorgio Not my downvote, but just a guess: I think most programmers feel, that recursion implies there is a recursive function call, because, well, that's what recursion is, a function calling itself. In a loop, there is no recursive function call. So saying that a loop without recursive function call is a special form of recursion would be blatantly wrong, if going by this definition. – hyde Jul 25 '16 at 8:48
  • 1
    Well, maybe looking to it from a more abstract point of view, what seem to be different things, are actually conceptually the same. I find it pretty discouraging and sad to think that people downvote answers just because they do not correspond to their expectations instead of taking them as a chance to learn something. All the answers that try to say: "Hey, look, these things look different on the surface, but are actually the same at a more abstract level" have been downvoted. – Giorgio Jul 25 '16 at 8:58
  • 3
    @Georgio: The purpose of this site is to get answers to questions. Answers which are helpful and correct deserve upvotes, answers which are confusing and unhelpful deserve downvotes. An answer which subtly uses a different definition of a common term without making it clear what different definition is used is confusing and unhelpful. Answers which only makes sense if you already know the answer, so to speak, are not helpful, and only serves to show the writers superior grasp of terminology. – JacquesB Jul 25 '16 at 9:03
  • 2
    @JacquesB: "Answers which only makes sense if you already know the answer, so to speak, are not helpful...": This can also be said of answers that only confirm what the reader already knows or thinks to know. If an answer introduces terminology that is not clear, it is possible to write comments to ask for more details before downvoting. – Giorgio Jul 25 '16 at 9:11
  • 4
    Loops are not a special form of recursion. Look at computability theory and e.g. the theoretical WHILE language and µ-calculus. Yes, some languages use loops as syntactic sugar to actually use recursion behind the scenes, but they can do that because recursion and iteration are equally expressive, not because they are the same. – Polygnome Jul 25 '16 at 11:03
-1

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.

  • 2
    You are talking about the implementation of a procedure call and of a while loop and, since they are implemented differently, you conclude that they are different. However, conceptually the are very similar. – Giorgio Jul 25 '16 at 4:49
  • 1
    Depending on compiler, an optimized, inlined recursion call might well produce the same assembly, as plain loop. – hyde Jul 25 '16 at 7:25
  • @hyde ... which is only an example for the well-known fact that one can be expressed through the other; doesn't mean they are identical. A bit like mass and energy. Of course one can argue that all ways to produce identical output are "the same". If the world were finite, all programs would be constexpr, in the end. – Peter A. Schneider Jul 25 '16 at 10:59
  • @Giorgio Nah, it's a logical description, not an implementation. We know that the two things are equivalent; but equivalence is not identity, because the question (and the answers) is exactly how we get to the result, i.e. they necessarily contain algorithmic descriptions (which can be expressed in terms of stack and variable etc.). – Peter A. Schneider Jul 25 '16 at 11:05
  • 1
    @PeterA.Schneider Yeah, but this answer states "Most important of all...different assembly code", which is not quite right. – hyde Jul 25 '16 at 12:30
-1

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

protected by Community Jul 25 '16 at 4:33

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.