DEV Community 👩‍💻👨‍💻

Discussion on: JavaScript: What the **** is Recursion?

Collapse
 
katafrakt profile image
Paweł Świątkowski • Edited on

Recursion can always be implemented as a loop

I'm not sure this is true, especially for tree-like structures. For example: find the first file named "treasure.js" in directory "projects" and all it's subdirectories.

Collapse
 
610470416 profile image
NotFound404

It is definitely wrong.
But recursion can always be implemented by a stack.
Because functions are implemented by stacks.

Collapse
 
tracygjg profile image
TGJ Gilmore • Edited on

I agree with Pawel, there are problems loops cannot solve and where recursion is a more efficient strategy. In your example Adam, you only make one recursive call from the function but there are also use case where a function might call itself more than once per cycle. The graphical flood fill algorithm is a good example.

Collapse
 
miketalbot profile image
Mike Talbot

Not sure about all cases, but you can definitely do your example without the need for a stack, but using a loop to create an array of folders to search etc. I just did a similar thing creating a tree that needed an final unrolled array rather than a recursive structure.

Collapse
 
katafrakt profile image
Paweł Świątkowski

So like with a while and current_directory variable and directories mutable array?

Thread Thread
 
miketalbot profile image
Mike Talbot

Yeah, probably no need for the directories array to be mutable though, you'd just replace it on each iteration with all of the next level down directories.

Thread Thread
 
peerreynders profile image
peerreynders

The quick and dirty trick I use:

  • Use an index i to track your working position in the array
  • Just push any "to be processed later" items onto the array
  • advance i on each iteration
  • done when i >= array.length

JSFiddle
Explanation

Thread Thread
 
nstvnsn profile image
Nathan Stevenson

Just for the sake of semantics, but arrays in JS are mutable by design!