6 ms·

Because you get a stack for free. It's very natural for depth first search of a tree.

ncmncm 5y ago
Unpleasant fact best learned early: the stack is not free. The "very natural" appearance is an artifact of the languages we have (very unnaturally) constructed.
- titzer 5y ago
  The machine stack given by modern CPUs is blazingly fast, because microarchitectures typically have a return stack buffer that allows the processor to perfectly branch-predict returns. Manually coding recursive algorithms means you have to switch over the return state, which involves a different predictor that will be less accurate. Given that, and machines typically have an architectural stack pointer register with dedicated instructions to push and pop to it, the manual datastructure you come up with to simulate a stack is almost certainly going to be slower.
  - ncmncm 5y ago
    It is always an error to assume you know which of any architectural alternatives will be faster. You have to measure, if it matters.
    - titzer 5y ago
      Please do. This is my prediction based on years and years of optimizing machine code and measuring on recent microarchitectures. I look forward to seeing your handwritten assembly proving your overgeneralized claims about recursion being inherently slower.
      - ncmncm 5y ago
        I did not, in fact, claim that recursion is inherently slower than iteration. You are welcome to read what I did write, above. Usually it is considered better (hint, hint) to do that before replying.
        titzer 5y ago
        You wrote: "the stack is not free." Which is even more vague (and broad) than what I was talking about. Given that we are talking about converting recursive algorithms into iterative versions that nevertheless use a stack datastructure, the comparison between the machine stack (used for recursion) and a program-defined stack is a perfectly appropriate criteria to evaluate your vague statement. I gave specific microarchitectural reasons why I predict the machine stack will be faster and you responded (a fairly reasonable response) that we should measure. So please do. I'm not the one making broad claims so the burden of proof still lies on you.
        ncmncm 5y ago
        It is a pure fact that the stack is not free. That it is heavily optimized is itself proof of the fact; you don't optimize what is already free. And, especially for heavily optimized features, you can only meaningfully measure specific cases, so generalizing is generally wrong. Which was the point of my remark.

Unpleasant fact best learned early: the stack is not free. The "very natural" appearance is an artifact of the languages we have (very unnaturally) constructed.

titzer 5y ago
The machine stack given by modern CPUs is blazingly fast, because microarchitectures typically have a return stack buffer that allows the processor to perfectly branch-predict returns. Manually coding recursive algorithms means you have to switch over the return state, which involves a different predictor that will be less accurate. Given that, and machines typically have an architectural stack pointer register with dedicated instructions to push and pop to it, the manual datastructure you come up with to simulate a stack is almost certainly going to be slower.
- ncmncm 5y ago
  It is always an error to assume you know which of any architectural alternatives will be faster. You have to measure, if it matters.
  - titzer 5y ago
    Please do. This is my prediction based on years and years of optimizing machine code and measuring on recent microarchitectures. I look forward to seeing your handwritten assembly proving your overgeneralized claims about recursion being inherently slower.
    - ncmncm 5y ago
      I did not, in fact, claim that recursion is inherently slower than iteration. You are welcome to read what I did write, above. Usually it is considered better (hint, hint) to do that before replying.
      - titzer 5y ago
        You wrote: "the stack is not free." Which is even more vague (and broad) than what I was talking about. Given that we are talking about converting recursive algorithms into iterative versions that nevertheless use a stack datastructure, the comparison between the machine stack (used for recursion) and a program-defined stack is a perfectly appropriate criteria to evaluate your vague statement. I gave specific microarchitectural reasons why I predict the machine stack will be faster and you responded (a fairly reasonable response) that we should measure. So please do. I'm not the one making broad claims so the burden of proof still lies on you.
        ncmncm 5y ago
        It is a pure fact that the stack is not free. That it is heavily optimized is itself proof of the fact; you don't optimize what is already free. And, especially for heavily optimized features, you can only meaningfully measure specific cases, so generalizing is generally wrong. Which was the point of my remark.