Iterative recursion

Published on: 2025-07-18

A systematic way to translate recursive algorithms to iterative ones.

By Tom Hulton-Harrop

recursion

iteration

c++

algorithms

Topic

When it comes to recursion, there’s an oft quoted phrase that goes…

“Every recursive algorithm can be written iteratively.”

That’s a true statement, but not a particularly helpful one. It’s not often that sentence is followed by examples, it’s usually followed by trust me. This had been bothering me lately, so I decided to try and understand how to reliably and repeatedly take a recursive algorithm, and convert it to an iterative one. What follows is one such approach I’ve now applied successfully in a number of cases.

TLDR: See the recursion-experiments repo for a ton of examples of the following technique in action.

Aside: This post owes much to Al Sweigart, author of the excellent book The Recursive Book of Recursion. Reading it really helped me clarify my thinking about recursion (and dust off some of the cobwebs). It also contained some helpful early examples of converting recursive algorithms to iterative ones in Python and JavaScript.

All the examples given below are in C++, but should be transferable to any other procedural language of your choosing.

Motivation

Recursive algorithms abound in computer science literature and on platforms like LeetCode, as well as puzzles such as Advent of Code (where the initial inspiration for this investigation came from). They are often incredibly succinct, and can be quite beautiful at times, but the problem is (at least in my experience) they aren’t something you’d want to use in production code due to the inherent risk of running out of stack space.

With that being said, it would be really nice if we could take a recursive algorithm more or less as-is, and without too much effort, convert it to an iterative one.

I feel like I’ve found one approach to achieve this. It’s definitely not perfect, and it’s almost certainly possible to create a more efficient bespoke iterative alternative, but from a pragmatic standpoint this could be useful to use when you want to take an off the shelf recursive algorithm and convert it to an iterative one.

From recursive to iterative

We’re going to start with one of the best known recursive algorithms, and that’s how to calculate the factorial of a number (e.g. 5! = 5 x 4 x 3 x 2 x 1 = 120). We’re starting with this one because it’s short, simple, and there’s only one recursive call we need to worry about.

Before we look at the recursive version and how to directly translate it to an iterative one, it’s worth quickly seeing the regular iterative version ¹.

1
int factorial_iterative(int n) {
2
  int fact = 1;
3
  for (; n > 0; n--) {
4
    fact *= n;
5
  }
6
  return fact;
7
}

The above is just a toy example, but it’s a good place to start from. The recursive version is as follows.

1
int factorial_recursive(int n) {
2
  if (n <= 1) {
3
    return 1;
4
  }
5
  return n * factorial_recursive(n - 1);
6
}

This version nicely demonstrates the two key pieces of a recursive algorithm. First, we have the base case.

1
int factorial_recursive(int n) {
2

3
  if (n <= 1) {
4
    return 1;
5
  }
6
  return n * factorial_recursive(n - 1);
7
}

And second, the recursive case.

1
int factorial_recursive(int n) {
2
  if (n <= 1) {
3
    return 1;
4
  }
5

6
  return n * factorial_recursive(n - 1);
7
}

In addition to only having one recursive call, the only variable we need to worry about is the function parameter, n.

1
int factorial_recursive(int n) {
2
  if (n <= 1) {
3
    return 1;
4
  }
5
  return n * factorial_recursive(n - 1);
6
}

There are four key pieces of information we need to keep track of in what we’ll call our ‘iterative recursive’ function.

Callstack
Function parameters
Return value
Return address

Let’s build up the function piece by piece, adding code to track the items from the above list.

We’ll start with a function declaration, with a signature that matches the recursive version we saw earlier.

1
int factorial_iterative_recursive(int n) {
2
  // todo
3
}

We know we’ll need an explicit callstack, and a structure to hold the function parameters and any local variables, so we’ll add those first.

1
int factorial_iterative_recursive(int n) {
2
  struct frame_t {
3
    int n;
4
  };
5
  std::stack<frame_t> call_stack;
6
  // todo
7
}

This (mostly) takes care of the callstack and function parameters from our list. Next we need a return value, as well as a way to process the stack.

1
int factorial_iterative_recursive(int n) {
2
  struct frame_t {
3
    int n;
4
  };
5
  std::stack<frame_t> call_stack;
6
  int return_value;
7
  while (!call_stack.empty()) {
8
    // todo
9
  }
10
  return return_value;
11
}

We’ve now accounted for the return value, as well as a way to process elements in our stack. All that remains is to deal with the return address. This is where things get interesting…

Whenever a regular function is called, behind the scenes the return address of the function is pushed onto the callstack. This is so the program knows where to continue from when the called function returns. If we return to the recursive implementation of factorial for a moment, when we call the function, execution will start at the entry point of the function on line 3.

1
int factorial_recursive(int n) {
2

3
  if (n <= 1) {
4
    return 1;
5
  }
6
  return n * factorial_recursive(n - 1);
7
}

However, when factorial_recursive(n - 1) returns, execution begins (or more accurately continues), at a later point in the function. If we introduce a local variable for the return value of factorial_recursive(n - 1), it’s a little clearer to see where this is happening (line 5 below). The return value of factorial_recursive(n - 1) is being written to the local variable, return_value.

1
int factorial_recursive(int n) {
2
  if (n <= 1) {
3
    return 1;
4
  }
5
  int return_value = factorial_recursive(n - 1);
6

7
  return n * return_value;
8
}

By switching to do things iteratively we have to handle this ourselves, which is why we must explicitly track the conceptual return address. Each time a fresh invocation of the factorial function is called, it hasn’t yet recorded a return address, it’s only when the function calls itself, the return address is recorded and pushed onto the stack.

To simulate a function call in our ‘iterative recursive’ case, we push a new frame onto the stack, setting its function parameters to be the same value as they’d be in the normal recursive case (n - 1).

// factorial_recursive(n - 1)
call_stack.push(frame_t{.n = top.n - 1});

The problem is we need a way to represent a return address which may not yet exist (later we’ll also need additional states for each recursive call). In the case of C++, std::optional is a very useful type for this, and we’ll use an enum to represent the separate recursive cases ².

To help keep things consistent for later, we’ll introduce a new enum called return_address_e, wrapped by a std::optional, default constructed to std::nullopt (meaning empty or unset).

Our function now looks like this.

1
int factorial_iterative_recursive(int n) {
2
  enum class return_address_e { recursive };
3
  struct frame_t {
4
    std::optional<return_address_e> return_address;
5
    int n;
6
  };
7
  std::stack<frame_t> call_stack;
8
  int return_value;
9
  while (!call_stack.empty()) {
10
    // todo
11
  }
12
  return return_value;
13
}

When we simulate a function call by pushing a new frame onto the stack, before we push the new value we need to record the return address, so when the ‘function’ returns (the frame is popped off the stack), we know where to continue from.

We can implement this like so.

call_stack.top().return_address = return_address_e::recursive;
call_stack.push(frame_t{.n = top.n - 1});

The optional will now contain a value, allowing us to take a separate code path the next time this frame is encountered.

We’ve added the new enum value, and we’re setting it when we call the function, we now just need to use it in our implementation. The key insight is that we need to divide our iterative version across the recursive call boundary, which means splitting the code from before the first recursive call into one branch (when no return address has been set), and the rest into another branch (when we know we have a valid return address).

Adding these branches we get the following.

1
int factorial_iterative_recursive(int n) {
2
  enum class return_address_e { recursive };
3
  struct frame_t {
4
    std::optional<return_address_e> return_address;
5
    int n;
6
  };
7
  std::stack<frame_t> call_stack;
8
  int return_value;
9
  while (!call_stack.empty()) {
10
    auto& top = call_stack.top();
11
    if (!top.return_address.has_value()) {
12
      // todo - before recursive call
13
    } else if (top.return_address == return_address_e::recursive) {
14
      // todo - after recursive call
15
    }
16
  }
17
  return return_value;
18
}

We’re super close now, the last bit is just implementing the logic from our recursive call (everything else has mostly just been boilerplate). Let’s start with the code before the recursive call (before the return address has been set), and then further divide that into the base case and the recursive case.

If we look at the base case on its own to start with, it looks like this.

if (top.n <= 1) {
  return_value = 1;
  call_stack.pop();
  continue;
}

This is equivalent to the recursive implementation below.

if (n <= 1) {
  return 1;
}

We set the return value to 1 (you can think of return_value as the space we’ve reserved to store the return value from our recursive function), we then pop the current stack frame off the stack (this simulates the function returning), and then the continue statement mimics the return by skipping all remaining code in the loop (we could use an else statement instead, but this keeps things a bit closer to the recursive version in style/appearance).

We’ve already seen the recursive case, as a quick reminder it looks like this.

auto& top = call_stack.top();
...
top.return_address = return_address_e::recursive;
call_stack.push(frame_t{.n = top.n - 1});

If we drop these new lines into place, we have the first half of our implementation (the code that runs the first time this function is called, or put another way, this frame is visited).

1
int factorial_iterative_recursive(int n) {
2
  enum class return_address_e { recursive };
3
  struct frame_t {
4
    std::optional<return_address_e> return_address;
5
    int n;
6
  };
7
  std::stack<frame_t> call_stack;
8
  int return_value;
9
  while (!call_stack.empty()) {
10
    auto& top = call_stack.top();
11
    if (!top.return_address.has_value()) {
12
      if (top.n <= 1) {
13
        return_value = 1;
14
        call_stack.pop();
15
        continue;
16
      }
17
      top.return_address = return_address_e::recursive;
18
      call_stack.push(frame_t{.n = top.n - 1});
19
    } else if (top.return_address == return_address_e::recursive) {
20
      // todo - after recursive call
21
    }
22
  }
23
  return return_value;
24
}

The final piece of the puzzle is to handle the logic after our recursive call returns, it’s essentially this part from the recursive version.

return n * return_value;

To update the return value of the current function call, we take the previous return value that was written to, multiply it by top.n, and then write that back to return_value so it’s updated. We then finally have to pop the current frame from the stack to conclude the return.

This looks as follows.

return_value = top.n * return_value;
call_stack.pop();

We can now slot everything into place and see the full ‘iterative recursive’ version of our factorial function.

1
int factorial_iterative_recursive(int n) {
2
  enum class return_address_e { recursive };
3
  struct frame_t {
4
    std::optional<return_address_e> return_address;
5
    int n;
6
  };
7
  std::stack<frame_t> call_stack;
8
  call_stack.push(frame_t{.return_address = std::nullopt, .n = n});
9
  int return_value; // uninitialised
10
  while (!call_stack.empty()) {
11
    auto& top = call_stack.top();
12
    if (!top.return_address.has_value()) {
13
      if (top.n <= 1) {
14
        return_value = 1;
15
        call_stack.pop();
16
        continue;
17
      }
18
      top.return_address = return_address_e::recursive;
19
      call_stack.push(frame_t{.n = top.n - 1});
20
    } else if (top.return_address == return_address_e::recursive) {
21
      return_value = top.n * return_value;
22
      call_stack.pop();
23
    }
24
  }
25
  return return_value;
26
}

It’s probably worth having a quick read through this to see all the individual pieces and how they fit together. It’s definitely a lot longer and busier than the terse recursive version we saw at the beginning, but the one thing it does have going for it is a good chunk of the implicit logic (that can at times feel a bit magic) is now visible. This makes understanding and debugging the code much easier, and in my mind helps better illuminate the recursive version as well.

The full code listing is also available on Compiler Explorer.

Now even though the above looks like a lot, the good news is this basic pattern maps to any recursive function you want to translate to iterative, with only minor adjustments needed depending on the recursive function you’re converting. Before we look at the general case, let’s review another classic recursive function and see how it maps to the ‘iterative recursive’ case.

The classic recursive function I’m referring to is of course Fibonacci, possibly the best known recursive function, while also being the slowest way to calculate the Fibonacci sequence (that being with the normal recursive version with no memoization).

First of all, before we look at the canonical recursive version of Fibonacci, let’s get the ‘proper’ iterative Fibonacci implementation out of the way.

1
int fibonacci_iterative(int n) {
2
  if (n <= 1) {
3
    return n;
4
  }
5
  int prev = 0;
6
  int curr = 1;
7
  for (int i = 1; i < n; i++) {
8
    int next = prev + curr;
9
    prev = curr;
10
    curr = next;
11
  }
12
  return curr;
13
}

On an unrelated note, you can replace lines 8-10 with std::exchange (quite possibly my favourite C++ utility function).

int next = prev + curr;
prev = curr;
curr = next;
prev = std::exchange(curr, prev + curr);

If for some bizarre reason you do need to calculate Fibonacci in your codebase, this is the way you’d do it. It’s fast, simple, and iterative.

Here is the classic recursive version of Fibonacci.

1
int fibonacci_recursive(int n) {
2
  if (n <= 1) {
3
    return n;
4
  }
5
  return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
6
}

This is slightly more interesting than the first recursive function we looked at to calculate factorial, because there are now two recursive calls happening instead of just one. Converting this to an iterative alternative right off the bat is a bit tricky, because as before, there’s quite a lot that’s hidden from us right now that we need to make explicit in the iterative version. Let’s make a couple of small changes to help with this.

1
int fibonacci_recursive(int n) {
2
  if (n <= 1) {
3
    return n;
4
  }
5
  int n_minus_1 = fibonacci_recursive(n - 1);
6
  int n_minus_2 = fibonacci_recursive(n - 2);
7
  return n_minus_1 + n_minus_2;
8
}

We’ve extracted the return values of each recursive call which will make converting things to the iterative version a bit easier. We’ll start with the rough outline of the ‘iterative recursive’ function we had before, and then make the necessary updates to have it handle calculating Fibonacci.

1
int fibonacci_iterative_recursive(int n)
2
  enum class return_address_e { /*return addresses*/ };
3
  struct frame_t {
4
    std::optional<return_address_e> return_address;
5
    int n; // function parameter
6
    /* any shared local variables */
7
  };
8
  std::stack<frame_t> call_stack;
9
  call_stack.push(frame_t{.n = n});
10
  int return_value = 0;
11
  while (!call_stack.empty()) {
12
    auto& top = call_stack.top();
13
    if (!top.return_address.has_value()) {
14
      // initial function call
15
    } else if (top.return_address == /* return address */) {
16
      // after first recursive call
17
    } else if (/* any other return addresses */) {
18
      // after second recursive call
19
    }
20
  }
21
  return return_value;
22
}

If we start with the return_address_e enum, because we have 2 recursive function calls, we know there are going to be two points as which we need to ‘resume’ our function, and two branches in addition to the initial call. We need a simple way to distinguish these so let’s just name the recursive_1 and recursive_2. While we’re at it we can fill in the branches we know we’ll need in our loop.

1
int fibonacci_iterative_recursive(int n)
2
  enum class return_address_e { recursive_1, recursive_2 };
3
  struct frame_t {
4
    std::optional<return_address_e> return_address;
5
    int n; // function parameter
6
    /* any shared local variables */
7
  };
8
  std::stack<frame_t> call_stack;
9
  call_stack.push(frame_t{.n = n});
10
  int return_value = 0;
11
  while (!call_stack.empty()) {
12
    auto& top = call_stack.top();
13
    if (!top.return_address.has_value()) {
14
      // initial function call
15
    } else if (top.return_address == return_address_e::recursive_1) {
16
      // after first recursive call
17
    } else if (top.return_address == return_address_e::recursive_2) {
18
      // after second recursive call
19
    }
20
  }
21
  return return_value;
22
}

In the recursive version we introduced two local variables, n_minus_1 and n_minus_2, to capture the return value of the recursive calls. When the lifetime of these variables extends across a recursive call (appearing before and after it), these variables need to be persisted so they retain the value they had when the function ‘resumes’. To accomplish this we simply need to add these variables to our frame_t structure.

struct frame_t {
  std::optional<return_address_e> return_address;
  int n;
  int n_minus_1;
  int n_minus_2;
};

Note: In this example, n_minus_2 is technically redundant. We could write the result of the function call directly to return_value, and then write return_value = top.n_minus_1 + return_value. It is included here as an attempt to help with readability.

Our partially implemented function now looks like this.

1
int fibonacci_iterative_recursive(int n)
2
  enum class return_address_e { recursive_1, recursive_2 };
3
  struct frame_t {
4
    std::optional<return_address_e> return_address;
5
    int n;
6
    int n_minus_1;
7
    int n_minus_2;
8
  };
9
  std::stack<frame_t> call_stack;
10
  call_stack.push(frame_t{.n = n});
11
  int return_value = 0;
12
  while (!call_stack.empty()) {
13
    auto& top = call_stack.top();
14
    if (!top.return_address.has_value()) {
15
      // initial function call
16
    } else if (top.return_address == return_address_e::recursive_1) {
17
      // after first recursive call
18
    } else if (top.return_address == return_address_e::recursive_2) {
19
      // after second recursive call
20
    }
21
  }
22
  return return_value;
23
}

We don’t need to worry about setting the new local variables yet. You could default initialise them if you wanted to (for peace of mind), but they only need to be set where they appear in the recursive call (that’s when the local variables will become ‘alive’ or in scope). We’re really just reserving space for them at the moment.

Now we just need to implement each branch of our function, corresponding to where in the recursive function we are. We’ll start with the first branch, when a new instance of the function is invoked. This includes the base case and first recursive case.

1
int fibonacci_iterative_recursive(int n)
2
  enum class return_address_e { recursive_1, recursive_2 };
3
  struct frame_t {
4
    std::optional<return_address_e> return_address;
5
    int n;
6
    int n_minus_1;
7
    int n_minus_2;
8
  };
9
  std::stack<frame_t> call_stack;
10
  call_stack.push(frame_t{.n = n});
11
  int return_value = 0;
12
  while (!call_stack.empty()) {
13
    auto& top = call_stack.top();
14
    if (!top.return_address.has_value()) {
15
      if (top.n <= 1) {
16
        return_value = top.n;
17
        call_stack.pop();
18
        continue;
19
      }
20
      top.return_address = return_address_e::recursive_1;
21
      call_stack.push(frame_t{.n = top.n - 1});
22
    } else if (top.return_address == return_address_e::recursive_1) {
23
      // after first recursive call
24
    } else if (top.return_address == return_address_e::recursive_2) {
25
      // after second recursive call
26
    }
27
  }
28
  return return_value;
29
}

This should all look strikingly familiar to the factorial version, the logic is nearly identical. The only difference is we’re setting return_value to n (instead of 1 in the factorial calculation), and the return address to return_address_e::recursive_1 instead of just return_address_e::recursive (as there’s more than one recursive call).

if (top.n <= 1) {
  return_value = top.n;
  call_stack.pop();
  continue;
}
top.return_address = return_address_e::recursive_1;
call_stack.push(frame_t{.n = top.n - 1});

The following branches are then just storing the return address before making the second recursive call, and finally updating the return value with n_minus_1 and n_minus_2.

The branch after the first recursive call is as follows.

top.return_address = return_address_e::recursive_2;
top.n_minus_1 = return_value;
call_stack.push(frame_t{.n = top.n - 2});

We update the return address, write the return value to n_minus_1, and then simulate calling the next function with n - 2.

The final branch is shown below.

top.n_minus_2 = return_value;
return_value = top.n_minus_1 + top.n_minus_2;
call_stack.pop();

We write the return value to n_minus_2 now (instead of the previous assignment to n_minus_1), we then update the return value with the result of n_minus_1 and n_minus_2, and finally we ‘return’ from the function by popping the current frame off the stack.

Our final function now looks like this.

int fibonacci_iterative_recursive(const int n) {
  enum class return_address_e { recursive_1, recursive_2 };
  struct frame_t {
    std::optional<return_address_e> return_address;
    int n;
    int n_minus_1;
    int n_minus_2;
  };
  std::stack<frame_t> call_stack;
  call_stack.push(frame_t{.n = n});
  int return_value = 0;
  while (!call_stack.empty()) {
    auto& top = call_stack.top();
    if (!top.return_address.has_value()) {
      if (top.n <= 1) {
        return_value = top.n;
        call_stack.pop();
        continue;
      }
      top.return_address = return_address_e::recursive_1;
      call_stack.push(frame_t{.n = top.n - 1});
    } else if (top.return_address == return_address_e::recursive_1) {
      top.return_address = return_address_e::recursive_2;
      top.n_minus_1 = return_value;
      call_stack.push(frame_t{.n = top.n - 2});
    } else if (top.return_address == return_address_e::recursive_2) {
      top.n_minus_2 = return_value;
      return_value = top.n_minus_1 + top.n_minus_2;
      call_stack.pop();
    }
  }
  return return_value;
}

And we’re done! It’s incredibly verbose, but it’s also weirdly satisfying to see a recursive algorithm exploded/unwrapped, with all the gory details in plain view (instead of elegantly/frustratingly hidden, depending on your perspective).

The full code listing is also available on Compiler Explorer.

Now we’ve been through two transformations from a recursive function to an iterative one, we can start to see how this applies more generally to all recursive functions. Below is a walkthrough of a generic ‘iterative recursive’ function.

1
2
/* return type */ iterative_recursive_placeholder(/*recursive function parameters*/) {
3

4
  enum class return_address_e { recursive[_n] };
5

6
  struct frame_t {
7
    // return address
8
    std::optional<return_address_e> return_address;
9
    // function parameters
10
    // shared local variables
11
  };
12

13
  std::stack<frame_t> call_stack;
14
  call_stack.push(frame_t{/* function parameters */});
15

16
  /* return type */ return_value  /* = uninitialised */;
17

18
  while (!call_stack.empty()) {
19
    auto& top = call_stack.top();
20
    if (!top.return_address.has_value()) {
21

22
      if (/* base case condition */) {
23
        return_value = /* parameter, local variable or constant */;
24
        // pop and continue (equivalent to early return)
25
        call_stack.pop();
26
        continue;
27
      }
28

29
      // set return address (where to return to after the recursive call)
30
      top.return_address = return_address_e::recursive[_n];
31
      // set any local variables needed across recursive calls
32
      top./* local variables */ = /* state */
33
      // 'call' recursive function by pushing a new frame onto the stack
34
      // parameters will be set from current stack top variables
35
      call_stack.push(frame_t{/* recursive parameters */});
36

37
    } else if (top.return_address == return_address_e::recursive[_n]) {
38
      // update local variable
39
      top./* local variables */ = /* state */
40
      // write to return_value when the function returns
41
      return_value = top./* local variables */;
42
      // pop the stack to simulate the function returning
43
      call_stack.pop();
44
    }
45
  }
46

47
  return return_value;
48
}

This basic shape repeats itself no matter the recursive function. The act of transforming a recursive function becomes mechanical once you have these building blocks to hand.

Below is one more example of a recursive function and its equivalent ‘iterative recursive’ variant. The function will generate all possible variations of opening and closing parentheses. For example if 3 is passed to the function, you’ll receive the following output.

// ((())), (()()), (())(), ()(()), ()()()

The recursive implementation is as follows.

1
std::vector<std::string> balanced_parentheses_internal(
2
  int opening, int closing, std::string current) {
3
  if (opening == 0 && closing == 0) {
4
    return std::vector<std::string>(1, current);
5
  }
6
  std::vector<std::string> results;
7
  if (opening > 0) {
8
    auto r = balanced_parentheses_internal(opening - 1, closing, current + "(");
9
    results.insert(results.end(), r.begin(), r.end());
10
  }
11
  if (closing > opening) {
12
    auto r = balanced_parentheses_internal(opening, closing - 1, current + ")");
13
    results.insert(results.end(), r.begin(), r.end());
14
  }
15
  return results;
16
}
17

18
std::vector<std::string> balanced_parentheses_recursive(int parentheses_count) {
19
  return balanced_parentheses_internal(parentheses_count, parentheses_count, "");
20
}

The ‘iterative recursive’ version is considerably longer due to the explicit nature of everything, but it will give an identical result.

1
std::vector<std::string> balanced_parentheses_iterative_recursive(
2
  int parentheses_count) {
3
  enum class return_address_e { recursive_1, recursive_2 };
4
  struct frame_t {
5
    std::optional<return_address_e> return_address;
6
    // function parameters
7
    int opening;
8
    int closing;
9
    std::string current;
10
    // (shared) local variables
11
    std::vector<std::string> results;
12
  };
13
  std::stack<frame_t> call_stack;
14
  call_stack.push(
15
    frame_t{
16
      .closing = parentheses_count,
17
      .opening = parentheses_count,
18
      .current = ""});
19
  std::vector<std::string> return_value;
20
  while (!call_stack.empty()) {
21
    auto& top = call_stack.top();
22
    if (!top.return_address.has_value()) {
23
      if (top.opening == 0 && top.closing == 0) {
24
        return_value = std::vector<std::string>(1, top.current);
25
        call_stack.pop();
26
        continue;
27
      }
28
      if (top.opening > 0) {
29
        top.return_address = return_address_e::recursive_1;
30
        call_stack.push(
31
          frame_t{
32
            .opening = top.opening - 1,
33
            .closing = top.closing,
34
            .current = top.current + "("});
35
        continue;
36
      }
37
      if (top.closing > top.opening) {
38
        top.return_address = return_address_e::recursive_2;
39
        call_stack.push(
40
          frame_t{
41
            .opening = top.opening,
42
            .closing = top.closing - 1,
43
            .current = top.current + ")"});
44
        continue;
45
      }
46
      return_value = top.results;
47
      call_stack.pop();
48
    } else if (top.return_address == return_address_e::recursive_1) {
49
      top.results.insert(
50
        top.results.end(), return_value.begin(), return_value.end());
51
      if (top.closing > top.opening) {
52
        top.return_address = return_address_e::recursive_2;
53
        call_stack.push(
54
          frame_t{
55
            .opening = top.opening,
56
            .closing = top.closing - 1,
57
            .current = top.current + ")"});
58
        continue;
59
      }
60
      return_value = top.results;
61
      call_stack.pop();
62
    } else if (top.return_address == return_address_e::recursive_2) {
63
      top.results.insert(
64
        top.results.end(), return_value.begin(), return_value.end());
65
      return_value = top.results;
66
      call_stack.pop();
67
    }
68
  }
69
  return return_value;
70
}

The above example highlights two code blocks that are duplicated. This is because in the recursive version, the recursive call balanced_parentheses_internal(opening, closing - 1, current + ")"); can either be called the first time through the function, or after having called balanced_parentheses_internal(opening - 1, closing, current + "(");. This could be refactored and split out to avoid the duplication, but remains here to aid with readability.

Summary

That more or less covers everything. If you want equivalent logging to a recursive function printing at the start, just add a print statement to the first branch of the ‘iterative recursive’ version (the one without a return address). If you don’t care about return values and just want to traverse a tree or graph, you can delete all the return value stuff. There’s a little more work needed to handle recursive functions called from inside a loop (the enumeration is only needed for each recursive call as it appears in the source code). What is needed, is to track the loop index as part of the frame object. Examples of this can be found here, and a more complex case here.

We also haven’t covered memoization, however this is added in more or less the exact same way as it would be to the recursive version. An example of adding memoization to the ‘iterative recursive’ version of Fibonacci can be found here. If you’d like to learn more about memoization, I can highly recommend the book mentioned at the outset of this post, The Recursive Book of Recursion. There’s also a great video from freeCodeCamp that covers memoization and dynamic programming which goes into a lot more detail.

I hope this has proved interesting, and possibly may be helpful in future. Be that with understanding recursive algorithms themselves, or ensuring a recursive algorithm can be applied without exhausting a program’s stack space. A ton of examples from mergesort and quicksort, to combinations and permutations, can be found in the repository mentioned at the top of the article, recursion experiments.

This only works for relatively small numbers, if you need to output the factorial of larger numbers you’ll need something smarter. ↩
It would also be okay to add a separate enum value to represent the ‘start’ or ‘empty’ state of the return address, it’s just those aren’t actually return addresses themselves. The optional approach respects the distinction between elements and their absence, so we can represent an ‘empty’ set, without needing an ‘empty’ value added as part of the set. ↩

Iterative recursion

Topic

Motivation

From recursive to iterative

Summary

Footnotes