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

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).

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).

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

Wow, somehow I expected something complex.

Thanks a lot!

Lets say you have two functions. Function A and function B. Function A does a bunch of stuff and function B is executed in the middle of function A. Well when function B returns the program must remember the context of function A in order to execute the remaining steps. It does this by storing the entire context of function A on a stack. This is known as the 'call stack.' Essentially, all recursive functions can and usually are implemented using a stack.

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.

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.

Here's a mind bending thought. It is actually the loop that is syntactic sugar and recursion is the implementation.

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.

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.

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.

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.