Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

"The same computation recurs"

Hmm...you mean like in a loop?



Nope.

You can run, for example, bubble sort or insertion sort in a loop, always iterating over the same set of data (with some fixed amount of state) until the array is sorted.

Conversely and per definition, quicksort divides the data flow into subarrays and then sub-subarrays recursively which means that a plain single loop with constant space for state won't do. You need extra space for storing state and the amount of that extra space needed depends on the size of the input; logarithmically, in quicksort's case.

The implementation of recursion can vary but the control and data flow still does recur in a nested fashion.




Consider applying for YC's Fall 2026 batch! Applications are open till July 27.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: