Return to Answer

Are there any cases where a task can only be done using recursion, rather than a loop?

You can always turn recursive algorithm into a loop, which uses a Last-In-First-Out data structure (AKA stack) to store temporary state, because recursive call is exactly that, storing current state in a stack, proceeding with the algorithm, then later restoring the state. So short answer is: No, there are no such cases.

However, an argument can be made for "yes". Let's take a concrete, easy example: merge sort. You need to divide data in two parts, merge sort the parts, and then combine them. Even if you don't do an actual programming language function call to merge sort in order to do merge sort on the parts, you need to implement functionality which is identical to actually doing a function call (push state to your own stack, jump to start of loop with different starting parameters, then later pop the state from your stack).

Is it recursion, if you implement the recursion call yourself, as separate "push state" and "jump to beginning" and "pop state" steps? And the answer to that is: No, it still isn't called recursion, it is called iteration with explicit stack (if you want to use established terminology).

Note, this also depends on definition of "task". If task is to sort, then you can do it with many algorithms, many of which don't need any kind of recursion. If task is to implement specific algorithm, like merge sort , then above ambiguity applies.

So let's consider question, are there general tasks, for which there are only recursion-like algorithms. I can't answer that accurately, but some speculation: most recursive type tasks (such as traversing a tree) are basically graph tasks. It is possible to represent graphs as tables. Manipulating tables with loops is easy. So I speculate that any task should be doable with loops over tables, without using a stack for the algorithm. However, it might be much less efficient, in space or time.

Are there any cases where a task can only be done using recursion, rather than a loop?

You can always turn recursive algorithm into a loop, which uses a Last-In-First-Out data structure (AKA stack) to store temporary state, because recursive call is exactly that, storing current state in a stack, proceeding with the algorithm, then later restoring the state. So short answer is: No, there are no such cases.

However, an argument can be made for "yes". Let's take a concrete, easy example: merge sort. You need to divide data in two parts, merge sort the parts, and then combine them. Even if you don't do an actual programming language function call to merge sort in order to do merge sort on the parts, you need to implement functionality which is identical to actually doing a function call (push state to your own stack, jump to start of loop with different starting parameters, then later pop the state from your stack).

Is it recursion, if you implement the recursion call yourself, as separate "push state" and "jump to beginning" and "pop state" steps? And the answer to that is: No, it still isn't called recursion, it is called iteration with explicit stack (if you want to use established terminology).

Note, this also depends on definition of "task". If task is to sort, then you can do it with many algorithms, many of which don't need any kind of recursion. If task is to implement specific algorithm, like merge sort , then above ambiguity applies.

So let's consider question, are there general tasks, for which there are only recursion-like algorithms. From comment of @WizardOfMenlo under the question, Ackermann function is a simple example of that. So the concept of recursion stands on its own, even if it can be implemented with a different computer program construct (iteration with explicit stack).

Are there any cases where a task can only be done using recursion, rather than a loop?

You can always turn recursive algorithm into a loop, which uses a Last-In-First-Out data structure (AKA stack) to store temporary state, because recursive call is exactly that, storing current state in a stack, proceeding with the algorithm, then later restoring the state. So short answer is: no, there are no such cases.

However, an argument can be made for "yes". Let's take a concrete, easy example: merge sort. You need to divide data in two parts, merge sort the parts, and then combine them. Even if you don't do an actual programming language function call to merge sort in order to do merge sort on the parts, you need to implement functionality which is identical to actually doing a function call (push state to your own stack, jump to start of loop with different starting parameters, then later pop the state from your stack).

Is it recursion, if you implement the recursion call yourself, as separate "push state" and "jump to beginning" and "pop state" steps?

Note, this also depends on definition of "task". If task is to sort, then you can do it with many algorithms, many of which don't need any kind of recursion. If task is to implement specific algorithm, like merge sort , then above ambiguity applies.

So let's consider question, are there general tasks, for which there are only recursion-like algorithms. I can't answer that accurately, but some speculation: most recursive type tasks (such as traversing a tree) are basically graph tasks. It is possible to represent graphs as tables. Manipulating tables with loops is easy. So I speculate that any task should be doable with loops over tables, without using a stack for the algorithm. However, it might be much less efficient, in space or time.

Are there any cases where a task can only be done using recursion, rather than a loop?

You can always turn recursive algorithm into a loop, which uses a Last-In-First-Out data structure (AKA stack) to store temporary state, because recursive call is exactly that, storing current state in a stack, proceeding with the algorithm, then later restoring the state. So short answer is: No, there are no such cases.

However, an argument can be made for "yes". Let's take a concrete, easy example: merge sort. You need to divide data in two parts, merge sort the parts, and then combine them. Even if you don't do an actual programming language function call to merge sort in order to do merge sort on the parts, you need to implement functionality which is identical to actually doing a function call (push state to your own stack, jump to start of loop with different starting parameters, then later pop the state from your stack).

Is it recursion, if you implement the recursion call yourself, as separate "push state" and "jump to beginning" and "pop state" steps? And the answer to that is: No, it still isn't called recursion, it is called iteration with explicit stack (if you want to use established terminology).

Note, this also depends on definition of "task". If task is to sort, then you can do it with many algorithms, many of which don't need any kind of recursion. If task is to implement specific algorithm, like merge sort , then above ambiguity applies.

So let's consider question, are there general tasks, for which there are only recursion-like algorithms. I can't answer that accurately, but some speculation: most recursive type tasks (such as traversing a tree) are basically graph tasks. It is possible to represent graphs as tables. Manipulating tables with loops is easy. So I speculate that any task should be doable with loops over tables, without using a stack for the algorithm. However, it might be much less efficient, in space or time.

Are there any cases where a task can only be done using recursion, rather than a loop?

You can always turn recursive algorithm into a loop, which uses a Last-In-First-Out data structure (AKA stack) to store temporary state, because recursive call is exactly that, storing current state in a stack, proceeding with the algorithm, then later restoring the state. So short answer is: no, there are no such cases.

However, an argument can be made for "yes". Let's take a concrete, easy example: merge sort. You need to divide data in two parts, merge sort the parts, and then combine them. Even if you don't do an actual programming language function call to merge sort in order to do merge sort on the parts, you need to implement functionality which is identical to actually doing a function call (push state to your own stack, jump to start of loop with different starting parameters, then later pop the state from your stack).

Is it recursion, if you implement the recursion call yourself, as separate "push state" and "jump to beginning" and "pop state" steps?

Note, this also depends on definition of "task". If task is to sort, then you can do it with many algorithms, many of which don't need any kind of recursion. If task is to implement specific algorithm, like merge sort , then above ambiguity applies.

Are there any cases where a task can only be done using recursion, rather than a loop?

You can always turn recursive algorithm into a loop, which uses a Last-In-First-Out data structure (AKA stack) to store temporary state, because recursive call is exactly that, storing current state in a stack, proceeding with the algorithm, then later restoring the state. So short answer is: no, there are no such cases.

However, an argument can be made for "yes". Let's take a concrete, easy example: merge sort. You need to divide data in two parts, merge sort the parts, and then combine them. Even if you don't do an actual programming language function call to merge sort in order to do merge sort on the parts, you need to implement functionality which is identical to actually doing a function call (push state to your own stack, jump to start of loop with different starting parameters, then later pop the state from your stack).

Is it recursion, if you implement the recursion call yourself, as separate "push state" and "jump to beginning" and "pop state" steps?

Note, this also depends on definition of "task". If task is to sort, then you can do it with many algorithms, many of which don't need any kind of recursion. If task is to implement specific algorithm, like merge sort , then above ambiguity applies.

So let's consider question, are there general tasks, for which there are only recursion-like algorithms. I can't answer that accurately, but some speculation: most recursive type tasks (such as traversing a tree) are basically graph tasks. It is possible to represent graphs as tables. Manipulating tables with loops is easy. So I speculate that any task should be doable with loops over tables, without using a stack for the algorithm. However, it might be much less efficient, in space or time.