[Adverblessly]

Not OP, but they probably mean something like the following toy problem (in C++):

  struct BinTree {
    long value;
    BinTree *left;
    BinTree *right;
  };

  long long RecursiveDFSSum(BinTree *node) {
    if (NULL == node) {
      return 0;
    }
    return (long long)value + RecursiveDFSSum(node->left) + RecursiveDFSSum(node->right);
  }

  long long IterativeDFSSum(BinTree *tree) {
    std::vector<BinTree *> custom_stack;
    custom_stack.push_back(tree);
    long long value = 0;
    while (!custom_stack.empty()) {
      BinTree *node = *custom_stack.rbegin();
      custom_stack.pop_back();
      if (NULL != node) {
        value += node->value;
        custom_stack.push_back(node->left);
        custom_stack.push_back(node->right);
      }
    }
    return value;
  }

Did not check this actually compiles etc. but you get the point. Both ways will give you the same solution in the same way, time complexity, space complexity etc. but the second one is not bound by max call stack size (only by max heap size). Additionally, the second one is slightly more space efficient, since the recursive solution requires saving an entire call frame into the stack (e.g. stack pointer, return address) whereas the iterative solution just stores one pointer per stack item.

[dahart]

This is exactly right; thank you for providing the example. This is manual recursion in a heap allocated space.

If you were coding a DP problem, then custom_stack might have a fixed size you can pre-allocate, and it might also be 2 or 3-dimensional.

For some image-based recursion, your backtracking doesn’t even need to store real pointers in the stack frame. For example when I’ve written a flood fill, I can store the return pointer as a one pixel offset in as little as 2 or 3 bits, depending on whether I include diagonal pixels (4-surround vs 8-surround).

[akshat_h]

Thanks! I was getting confused between stack data structure, function stack and stack space and had gotten to a weird mix in my head. The example cleared it up.