5 ms·

Many commonly-used data structures (e.g. trees) are nearly impossible to manage without recursion.

by brianberns 10y ago

crimsonalucard 10y ago
Not true. A loop and a stack can achieve the same thing!
- ihoz 10y ago
  Recursion is nothing more than implicitly using a stack (via the call stack) or explicitly with a loop. You just won't get a stack overflow exception with the loop -- you'll run out of heap instead. It's still the stack filling up.
- vertex-four 10y ago
  Indeed. People who claim recursion is the only way to handle some types of data structures are missing how recursion is implemented. In practice, it boils down to a stack and a loop - and in the case of tail-recursive functions, not even the stack - though it may be a little prettier if you use recursion.
  - charles-salvia 10y ago
    Recursion sometimes makes it easier to implement certain algorithms, since modern programming languages have an implicit call stack which conveniently provides a snapshot of the state of all local stack variables at that point in the algorithm.
  - crimsonalucard 10y ago
    Here's a mind bending thought. It is actually the loop that is syntactic sugar and recursion is the implementation.
    - buzzybee 10y ago
      You're begging the question of what the lambda calculus is. As a theoretical basis for computing it sits equivalently with Turing machines. In practical use, there are consequences with trying to represent the computation with one or the other model, and our physical hardware resembles neither, really.
    - vertex-four 10y ago
      In practice, lambda calculus machines are rare, and your code probably compiles down to machine code that more closely emulates a loop and a stack. I'm not saying they're not theoretically equivalent, of course.
- auxym 10y ago
  As an amateur programmer, I'm intrigued in how this is achieved, would you happen to have any references you could point me to? My first encounter with recursion was when I needed to traverse a directory tree. I couldn't figure how to go arbritrarily deep without writing tens of nested for-loops. Then recursion somehow hit me, or I found something interesting on Google, can't remember, it was over 10 years ago, pretty sure SO wasn't around. ...and then a while later I found out about os.walk (this was python).
  - clusmore 10y ago
    Here's a recursive directory traversal in Python: import os import os.path def list_files_recursive(path): filenames = os.listdir(path) for filename in filenames: fullname = os.path.join(path, filename) if os.path.isdir(fullname): yield from list_files_recursive(fullname) # recursively explore folders else: yield fullname and here is the same program with an explicit stack import os import os.path def list_files_stack(path): folders = [path] # create stack of unexplored folders while folders: # repeat until stack is empty path = folders.pop() # pick a folder from stack filenames = os.listdir(path) for filename in filenames: fullname = os.path.join(path, filename) if os.path.isdir(fullname): folders.append(fullname) # push folder to stack else: yield fullname
    - auxym 10y ago
      Wow, somehow I expected something complex. Thanks a lot!
  - thethirdone 10y ago
    http://blog.moertel.com/ http://blog.moertel.com/ does a decent job of explaining some practical aspects for de-recursivying, but I'll give you a basic explanation of that plus a more theoretical answer showing that any computatble function can be written using only while loops and a stack. Practical: If we right all of are programs and tail-recursive (returning a recursive call or constant at the end of the prgram) programs they are easy to transform into simple while loops with no stack. The idea is instead of calling another function just restart the current one with the updated arguments. EX: f(n,x)=f(n-1,x+1) f(0,x)=x goes to while(n > 0){ n--; x++ } Other techniques such as trampolining and continuation passing style also help translate recursive functions into iterative ones. Theorectical: Think about Brainfuck or Turing machines, these computing frameworks can compute any computable function using only what amounts to while loops and infinite memory. Given then that we can produce arbitrary control flow using only while loops, we can reproduce how recursive calls are computed in computers with stack frames (provided by our stack).
- dreamcompiler 10y ago
  For many algorithms you'll have to build and maintain a stack manually if you use a loop. I once saw an old Fortran routine that expressed Quicksort this way.

Many commonly-used data structures (e.g. trees) are nearly impossible to manage without recursion.

crimsonalucard 10y ago

Not true. A loop and a stack can achieve the same thing!

ihoz 10y ago
Recursion is nothing more than implicitly using a stack (via the call stack) or explicitly with a loop. You just won't get a stack overflow exception with the loop -- you'll run out of heap instead. It's still the stack filling up.
vertex-four 10y ago
Indeed. People who claim recursion is the only way to handle some types of data structures are missing how recursion is implemented. In practice, it boils down to a stack and a loop - and in the case of tail-recursive functions, not even the stack - though it may be a little prettier if you use recursion.
- charles-salvia 10y ago
  Recursion sometimes makes it easier to implement certain algorithms, since modern programming languages have an implicit call stack which conveniently provides a snapshot of the state of all local stack variables at that point in the algorithm.
- crimsonalucard 10y ago
  Here's a mind bending thought. It is actually the loop that is syntactic sugar and recursion is the implementation.
  - buzzybee 10y ago
    You're begging the question of what the lambda calculus is. As a theoretical basis for computing it sits equivalently with Turing machines. In practical use, there are consequences with trying to represent the computation with one or the other model, and our physical hardware resembles neither, really.
  - vertex-four 10y ago
    In practice, lambda calculus machines are rare, and your code probably compiles down to machine code that more closely emulates a loop and a stack. I'm not saying they're not theoretically equivalent, of course.
auxym 10y ago
As an amateur programmer, I'm intrigued in how this is achieved, would you happen to have any references you could point me to? My first encounter with recursion was when I needed to traverse a directory tree. I couldn't figure how to go arbritrarily deep without writing tens of nested for-loops. Then recursion somehow hit me, or I found something interesting on Google, can't remember, it was over 10 years ago, pretty sure SO wasn't around. ...and then a while later I found out about os.walk (this was python).
- clusmore 10y ago
  Here's a recursive directory traversal in Python: import os import os.path def list_files_recursive(path): filenames = os.listdir(path) for filename in filenames: fullname = os.path.join(path, filename) if os.path.isdir(fullname): yield from list_files_recursive(fullname) # recursively explore folders else: yield fullname and here is the same program with an explicit stack import os import os.path def list_files_stack(path): folders = [path] # create stack of unexplored folders while folders: # repeat until stack is empty path = folders.pop() # pick a folder from stack filenames = os.listdir(path) for filename in filenames: fullname = os.path.join(path, filename) if os.path.isdir(fullname): folders.append(fullname) # push folder to stack else: yield fullname
  - auxym 10y ago
    Wow, somehow I expected something complex. Thanks a lot!
- thethirdone 10y ago
  http://blog.moertel.com/ http://blog.moertel.com/ does a decent job of explaining some practical aspects for de-recursivying, but I'll give you a basic explanation of that plus a more theoretical answer showing that any computatble function can be written using only while loops and a stack. Practical: If we right all of are programs and tail-recursive (returning a recursive call or constant at the end of the prgram) programs they are easy to transform into simple while loops with no stack. The idea is instead of calling another function just restart the current one with the updated arguments. EX: f(n,x)=f(n-1,x+1) f(0,x)=x goes to while(n > 0){ n--; x++ } Other techniques such as trampolining and continuation passing style also help translate recursive functions into iterative ones. Theorectical: Think about Brainfuck or Turing machines, these computing frameworks can compute any computable function using only what amounts to while loops and infinite memory. Given then that we can produce arbitrary control flow using only while loops, we can reproduce how recursive calls are computed in computers with stack frames (provided by our stack).
dreamcompiler 10y ago
For many algorithms you'll have to build and maintain a stack manually if you use a loop. I once saw an old Fortran routine that expressed Quicksort this way.