4 ms·

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 recursi

by 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).
crimsonalucard 10y ago
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.

by auxym 10y ago

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

crimsonalucard 10y ago

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.