DEV Community

Cover image for Anonymous Recursion in JavaScript
simo
simo

Posted on • Updated on

Anonymous Recursion in JavaScript

(
  (
    (f) => f(f)
  )
  (
    (f) =>
      (l) => {
        console.log(l)
        if (l.length) f(f)(l.slice(1))
        console.log(l)
      }
  )
)
(
  [1, 2, 3]
)
Enter fullscreen mode Exit fullscreen mode

Yes, there is such thing, and I thought it would be an interesting example to share. It features: closures, self-executing functions, arrow functions, functional programming, and anonymous recursion.

You can copy/paste the above example in your browser's console. The output is as follows:

[ 1, 2, 3 ]
[ 2, 3 ]
[ 3 ]
[]
[]
[ 3 ]
[ 2, 3 ]
[ 1, 2, 3 ]
Enter fullscreen mode Exit fullscreen mode

Speaking of functional programming, here is how similar example look like in Scheme (one of the languages JavaScript was influenced by):

(
  (
    (lambda (f) (f f))
    (lambda (f)
      (lambda (l)
        (print l)
        (if (not (null? l)) ((f f) (cdr l)))
        (print l)
      )
    )
  )
  '(1 2 3)
)
Enter fullscreen mode Exit fullscreen mode

Unwind

Like in many other programming languages calling a function is done by appending parentheses () after its name:

function foo () { return 'hey' }
foo()
Enter fullscreen mode Exit fullscreen mode

In JavaScript we can wrap any number of expressions in parentheses:

('hey', 2+5, 'dev.to')
Enter fullscreen mode Exit fullscreen mode

The result of the above snippet is 'dev.to'. The reason why is because JavaScript returns the last expression as result.

Wrapping a single anonymous (lambda) function in parentheses () means that the result will be the anonymous function itself:

(function () { return 'hey' })
Enter fullscreen mode Exit fullscreen mode

That in itself is not very useful because the anonymous function does not have a name, and we won't be able to reference it unless we call it immediately during initialization.

Like a regular function, we can append parentheses () after it to call it:

(function () { return 'hey' })()
Enter fullscreen mode Exit fullscreen mode

The same goes with the arrow functions:

(() => 'hey')()
Enter fullscreen mode Exit fullscreen mode

Again, appending parentheses () after the anonymous function means that we are executing it, also known as self-executing function.

Closures

A closure is the combination of a function and the lexical environment within which that function was declared. Combined with arrow functions we can define it like this:

var foo = (hi) => (dev) => hi + ' ' + dev
Enter fullscreen mode Exit fullscreen mode

Calling the above function in the browser's console will print 'hey dev.to':

foo('hey')('dev.to')
Enter fullscreen mode Exit fullscreen mode

Note that we have access to the hi argument from the outer scope of the enclosing function inside the enclosed inner one.

The above code is identical to:

function foo (hi) {
  return function (dev) { return hi + ' ' + dev }
}
Enter fullscreen mode Exit fullscreen mode

And the self-executing version would be:

(
  (hi) =>
    (
      (dev) => `${hi} ${dev}`
    )
    ('dev.to')
)
('hey')
Enter fullscreen mode Exit fullscreen mode

First the hey parameter is passed to the outermost scope to the above function as hi argument. Then that function returns yet another self-executing function that needs to be evaluated first. The dev.to parameter is then passed as the dev argument to the innermost function, and that function return the final result: 'hey dev.to'.

Going Deep

Here is a slightly modified version of the above self-executing function:

(
  (
    (dev) =>
      (hi) => `${hi} ${dev}`
  )
  ('dev.to')
)
('hey')
Enter fullscreen mode Exit fullscreen mode

First the hey parameter is passed as argument to the outermost scope, but instead of a function there we have yet another expression that needs to be evaluated first. So the dev.to parameter is then passed to the inner self-executing function as the dev argument and returns another function. That last function is what satisfies the outermost scope and therefore receives the hey parameter.

It's important to note that the self-executing functions and closures are used to initialize and encapsulate state, and this is what we're going to use in our next example.

Anonymous Recursion

Going back to our initial example, this time annotated:

(
  (
    (f) => f(f) // 3.
  )
  (
    (f) => // 2.
      (l) => { // 4.
        console.log(l)
        if (l.length) f(f)(l.slice(1))
        console.log(l)
      }
  )
)
(
  [1, 2, 3] // 1.
)
Enter fullscreen mode Exit fullscreen mode
  1. The input array [1, 2, 3] is passed to the outermost scope
  2. This entire function is passed as argument to the function above
  3. This function receives the bottom one as argument f and calls it with itself
  4. 2. being called in 3. results in returning the 4. function which is the one that satisfies the outermost scope and therefore receives the input array as the l argument

The reason for all of this is to have a reference to the f function inside the recursive one that receives the input array l. That way we can call it:

f(f)(l.slice(1))
Enter fullscreen mode Exit fullscreen mode

Note that f is a closure so we need to call it with itself just to get access to the innermost function that operates on the input array.

For explanatory purposes the first console.log(l) statement represents the recursive top-down, and the second one the recursive bottom-up.

Conclusion

I hope you enjoyed this article and learned something new out of it. Closures, self-executing functions and functional programming patterns are not black magic. They follow simple principles that are easy to understand and fun to play with.

That being said you have to develop a sense of your own when to use them, or not. If your code becomes harder to maintain, then it's probably a good idea to refactor it a little bit.

Nevertheless understanding these fundamental techniques is pivotal to creating clean and elegant solutions, as well as leveling up.

Happy Coding!

Top comments (12)

Collapse
 
thereversengineer profile image
the-reversengineer

Hi. Thank you.

Only one suggestion: maybe the "self executing function" should be:

(
  (hi) =>
    (
      (dev) => `${hi} ${dev}`
    )
)
('hey')
('dev.to')
Enter fullscreen mode Exit fullscreen mode
Collapse
 
simov profile image
simo

That would work too. And it's looking good.

Collapse
 
thereversengineer profile image
the-reversengineer

Not only, but it better separates the code term (one) from the input terms (two of them).

In my version, you can see that all the long consecutive block:

(
  (hi) =>
    (
      (dev) => `${hi} ${dev}`
    )
)
Enter fullscreen mode Exit fullscreen mode

is the code term as a whole, and the next two terms are inputs.
Getting all the "input" as a whole ensures portability (that is, you can take that self-sufficient code and use somewhere else).

For any novice reader of my reply: in JavaScript (and, more in general, in classical lambda-calculus theory), the convention is to left-associate terms together in more-than-two-items sequences, so the two input terms cannot be grouped in one term only (like we did for the code one).

A fully parenthesiszed equivalent expression would be:

(
  (
    (
      (hi) =>
        (
          (dev) => `${hi} ${dev}`
        )
    )
    ('hey')
  )
  ('dev.to')
)
Enter fullscreen mode Exit fullscreen mode

indeed.

The outermost parentheses, in my notation, indicates that we want to reduce (or, in classical programming languages speaking, to run) what's inside of them.


Regarding my first reply, I was just comparing your version of the invocation code (the one with the 'dev.to' term inside the function to be returned) with this other invocation
foo('hey')('dev.to')
you wrote right before.

Simply, my version applies the arguments like this 😊.
Regards.

Thread Thread
 
simov profile image
simo

Now I see, I was looking at the Going Deep example where I intentionally wanted to nest the arguments, so that the example resembles more closely the Anonymous Recursion one below it.

I should probably update the example in the Closures chapter. Thanks for the feedback!

Collapse
 
yuriss profile image
Yuri Santos • Edited

Correct me if I'm wrong.
Function that returns another function is high order function not a closure. Closure relates to scope and not to return.

Collapse
 
bitwiselover profile image
undefined

That is absolutely correct, a closure has access to the function environment (scope) of it's parent. A higher-order function can be described as a function that accepts a function as an argument and/or returns a function.

Collapse
 
simov profile image
simo • Edited

Thank you for your input!

I've fixed the definition, this time I got it straight from MDN just to make sure I'm not mistaken something.

Collapse
 
proddi profile image
proddi

Usually this is a perfect example howto to not write code. But for an interview it's great!

Collapse
 
simov profile image
simo

I agree, the anonymous recursion is a bit extreme and hard to maintain, though each part of this example taken separately is actually very useful in day to day programming.

Collapse
 
mechrisreed profile image
Chris Reed

You should bring up the y-combinator in there...

Collapse
 
ismagilovkamil profile image
Kamil

Hi, may i translate your article in Russian and publish it on my resource: lovefrontend.ru/ . I put links to your original article. Thanks.

Collapse
 
simov profile image
simo

Sure, if there is a link to the original article - then no problem.