Recursion - Looping or Vectorization
For some time now, this has been bugging me - so I thought to gather some more feedback/information/opinions on this.
What would you classify Recursion? As a loop or as a vectorized section of code?
For context, this query occured to me while creating Cody problems involving strict (so to speak) vectorization - (Everyone is more than welcome to check my recent Cody questions).
To make problems interesting and/or difficult, I (and other posters) ban functions and functionalities - such as for loops, while loops, if-else statements, arrayfun() and the rest of the fun() family functions. However, some of the solutions including the reference solution I came up with for my latest problem, contained recursion.
I am rather divided on how to categorize it. What do you think?
7 Comments
Time Descending
"What would you classify Recursion? As a loop or as a vectorized section of code?"
Neither.
I would vote to make it a third category, but if you insist on classifying recursion as either looping or vectorization, I would say looping.
My reason being that it should be possible with minimal boiler plate code to rewrite most (all?) recursive functions into a while loop.
Once uppon a time, I was taught that tail-recursion should be trivial to rewrite into a loop-algorithm, and that all recursions can be rewritten too. But as far as I understand something acting as a stack is necessary for divide-and-conquer algorithms like quick-sort just to keep track of the partition-indices and such. (Since I'm a wee bit lazy: it is so much easier to write it recursively and let the language handle that stuff...)
In my opinion, recursion is closer to looping, and does not count as vectorization. Vectorization involves SIMD (single instruction, multiple data), which is not the case for recursion: recursion almost always involves either the same size of input parameters or else input parameters that are shrunk by one or two elements.
"Operations-wise" recursion is not at all similar to vectorization, but in my opinion it would als be rather misleading to force the pattern into a looping category - in most divide-and-conquer algorithms, for example quicksort, the data is split into halves/parts and the task is solved by tree-like traversion through the data. In a choise between categorizing recursion as "vectorization" or "loop" I would answer neither.
Sign in to participate
