Consider a simple function that adds the first N natural numbers. (e.g. `sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15`

).

Here is a simple JavaScript implementation that uses recursion:

```
function recsum(x) {
if (x === 0) {
return 0;
} else {
return x + recsum(x - 1);
}
}
```

If you called `recsum(5)`

, this is what the JavaScript interpreter would evaluate:

```
recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15
```

Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.

Here's a tail-recursive version of the same function:

```
function tailrecsum(x, running_total = 0) {
if (x === 0) {
return running_total;
} else {
return tailrecsum(x - 1, running_total + x);
}
}
```

Here's the sequence of events that would occur if you called `tailrecsum(5)`

, (which would effectively be `tailrecsum(5, 0)`

, because of the default second argument).

```
tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15
```

In the tail-recursive case, with each evaluation of the recursive call, the `running_total`

is updated.

*Note: The original answer used examples from Python. These have been changed to JavaScript, since Python interpreters don't support tail call optimization. However, while tail call optimization is part of the ECMAScript 2015 spec, most JavaScript interpreters don't support it.*

Usually, I replace a recursive algorithm by an iterative algorithm by pushing the parameters that would normally be passed to the recursive function onto a stack. In fact, you are replacing the program stack by one of your own.

```
var stack = [];
stack.push(firstObject);
// while not empty
while (stack.length) {
// Pop off end of stack.
obj = stack.pop();
// Do stuff.
// Push other objects on the stack as needed.
...
}
```

Note: if you have more than one recursive call inside and you want to preserve the order of the calls, you have to add them in the reverse order to the stack:

```
foo(first);
foo(second);
```

has to be replaced by

```
stack.push(second);
stack.push(first);
```

Edit: The article Stacks and Recursion Elimination (or Article Backup link) goes into more details on this subject.

## Best Solution

I favor recursive solutions when:

The implementation of the recursion is much simpler than the iterative solution, usually because it exploits a structural aspect of the problem in a way that the iterative approach cannot

I can be reasonably assured that the depth of the recursion will not cause a stack overflow, assuming we're talking about a language that implements recursion this way

Condition 1 doesn't seem to be the case here. The iterative solution is about the same level of complexity, so I'd stick with the iterative route.