Solving dynamic programming interview problems

Post by pvg » Sat, May 19, 2018, 6:06 AM UTC

blackflame7000 wrote: post #98

throwaway37585 wrote: post #94

Earlier quoted context omitted.

> Whats complicated about an iteration What’s complicated about a recursion? > If you see problems, its because something is modifying it between runs, but that wasn't a fault of the iterative strategy, it was the fault of a bad programmer. > Conversely, you must always make sure the stopping condition and all base cases are met during recursion. You seem to be applying a double standard here. > Forget one corner bas…

Then why does NASA consider it unsafe for mission critical code? How about unknown potential stack size? How about factoring a large number with recursion? Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...

Post by blackflame7000 » Sat, May 19, 2018, 7:33 AM UTC

jacquesm wrote: post #101

blackflame7000 wrote: post #98

Earlier quoted context omitted.

Then why does NASA consider it unsafe for mission critical code? How about unknown potential stack size? How about factoring a large number with recursion? Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...

That's a restriction on the environment which has absolutely nothing to do with how readable a certain piece of code is. In fact it argues the opposite: we force you to use a less readable version of your code because the elegant one may be easier to read but it may have negative consequences due to implementation details. That's a really good trade-off for them but it does not necessarily help readability.

Post by jacquesm » Sat, May 19, 2018, 7:43 AM UTC

blackflame7000 wrote: post #123

jacquesm wrote: post #101

Earlier quoted context omitted.

That's a restriction on the environment which has absolutely nothing to do with how readable a certain piece of code is. In fact it argues the opposite: we force you to use a less readable version of your code because the elegant one may be easier to read but it may have negative consequences due to implementation details. That's a really good trade-off for them but it does not necessarily help readability.

But then your code is not portable because it is now susceptible to arbitrary stack depth changes blowing up your program. None of your arguments make sense when compared with the overwhelmingly superior iterative approach. Recursion is the same as iteration + downsides. I mean seriously name the last time you had a stack overflow and weren't doing recursion? That's an entire class of bug introduced or eliminated by…

Post by blackflame7000 » Sat, May 19, 2018, 7:49 AM UTC

pvg wrote: post #121

blackflame7000 wrote: post #98

Earlier quoted context omitted.

Then why does NASA consider it unsafe for mission critical code? How about unknown potential stack size? How about factoring a large number with recursion? Everything recursive can be transformed to iterative and yea sometimes it’s not as sexy but neither is a helmet https://www.reddit.com/r/programming/comments/3dnsh1/nasas_t...

Then why does NASA consider it unsafe for mission critical code? You started with the assertion iterative implementations were more intuitive and easier to read so this is a bit of goalpoast-moving. Write an iterative pseudocode DFS or quicksort. How 'intuitive' does that look?

Post by Adverblessly » Sat, May 19, 2018, 9:23 AM UTC

akshat_h wrote: post #120

dahart wrote: post #66

Earlier quoted context omitted.

Yes that, or code the recursive solution in a heap-allocated space rather than on the stack. It somehow seems easier, safer, and more explicit and controllable to me to adjust the code & data to use manual recursion with backtracking than try to adjust system stack limits. Often it consumes a lot less memory too, since you have more control over what your "stack frame" looks like; you don't have to store all your loc…

Any examples of code for this approach? From what I guess, you are implementing some kind of assembly like approach with explicit saving of stack frame, but I am having a hard time imagining it as being easier.

  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 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;
  }