Javascript closures and recursion

Question

I've been reading more specifically into the closure concept of programming, particularly pertaining to Javascript. I'm not quite there yet in understanding how it's any different from the Javascript code I've been writing for years though. I understand the concept of recursion as well, but I'm wondering, how are closures and recursion similar? Do I understand correctly that recursion, in and of itself, is a type of closure?

Closure:

function init() {
    var name = "Stack Overflow";
    function displayName() {
        alert(name);
    }
    displayName();
}
init();

Recursion:

function factorial(num) {
    if(num < 0)
        return -1;

    else if(num == 0)
        return 1;

    else
        return (num * factorial(num - 1));
}

alert(factorial(8));

I think I'm beginning to understand that a closure is nothing more than having a function within a function, with the inside function having access to the outside function via scoping. Could there be a recursive closure? I mean, while my example of recursion isn't exactly an example of closure as well, could it at least happen? I'm trying to understand how recursion and closures are similar, different, or if they're even comparable by all. Are there any examples to maybe describe this?

Any time you define a function, you make a closure. That's about the most similar the concepts are. — Denys Séguret, Jun 18 '13 at 16:52
Can you elaborate a bit more on your understanding thus far? It would make it easier to explain how they aren't related. — Brad, Jun 18 '13 at 16:52
Right now, it's hard to answer otherwise than by giving the definition of both concepts, and that's not the purpose of SO as those concepts are easy to google. — Denys Séguret, Jun 18 '13 at 16:53
A closure is a function that "closes around" (accesses) variables defined outside of that function. Recursion is when a function (that may or may not be a closure) calls itself. I wouldn't call them similar or different; they are unrelated to each other. — gen_Eric, Jun 18 '13 at 16:55
a recursion: suppose you have a picture of a person holding a box. on the box there is a picture of the same person holding the same box that has a picture on it. the picture includes itself. :) http://en.wikipedia.org/wiki/Droste_effect — akonsu, Jun 18 '13 at 17:07
I've updated my question to perhaps give a little bit more room to answer a particular question rather than explain a vague concept. — cereallarceny, Jun 18 '13 at 17:11
@cereallarceny: Your `factorial` function is not recursive. Here is an example of a recursive function: http://jsfiddle.net/kg5MT/. Notice how `factorial` calls itself. What you have is a `while` loop. — gen_Eric, Jun 18 '13 at 17:11
a closure is not a function inside a function. a closure is a function and its free variables (the variables that are external to the function) with their values captured at the moment when the function was invoked. — akonsu, Jun 18 '13 at 17:13
Pardon me, you're right. I've updated my question to actually... include recursion. What a concept. — cereallarceny, Jun 18 '13 at 17:14
@cereallarceny: Yep, that's recursion! It's got nothing to do with closures. `factorial` is only seeing the `num` variable passed to it, it has no knowledge of the `num` values from previous runs (or any other variable). It's not "closing around" (or capturing) any outside variables like your closure is doing. `displayName` is a closure because it's accessing the `name` variable that was declared outside its scope. — gen_Eric, Jun 18 '13 at 17:16
I understand now! Is there any particular way to have both closure and recursion in one? Perhaps if it's possible, is this maybe a bad idea? Also, don't be shy to put this in answer form, I'd rather have this on Stack Overflow for reference rather than have someone read through comments or close the question altogether. — cereallarceny, Jun 18 '13 at 17:18
@cereallarceny: Depends what you wanted to do. You could have a recursive closure if you really wanted to. — gen_Eric, Jun 18 '13 at 17:20

Mulan · Accepted Answer · 2016-08-10T15:37:14.150

A closure is simply a function or procedure that "closes over" an environment (it's body). In your code, init, displayName, and factorial are all closures. You use JavaScript function keyword (or now we have => arrow functions in ES6) when you want to create a closure.

Recursion is the effect of a procedure repeating itself

I've been reading a new book and it talks about some relevant topics. I thought I'd just share some notes here in case you were interested.

Here's a recursive function for calculating factorials. It does the same thing as yours but in a very different way. Let's see!

function factorial(x) {
  if (x < 0) throw Error("Cannot calculate factorial of a negative number");
  function iter(i, fact) {
    return i === 0 ? fact : iter(i-1, i*fact);
  }
  return iter(x, 1);
}

factorial(6); // 720

Compare it to the one you defined above ^.^. Notice that even though it's recursive, it doesn't call itself (factorial) again. This uses a linear iterative process that consumes linear space and time. The evaluation of the function looks something like this

factorial(6);
  iter(6, 1);
  iter(5, 6*1); 
  iter(4, 5*6);
  iter(3, 4*30);
  iter(2, 3*120);
  iter(1, 2*360);
  iter(0, 1*720);
// => 720

Compare that to the process of your function. Here's what yours would look like

factorial(6);
(6 * factorial(5));
(6 * (5 * factorial(4)));
(6 * (5 * (4 * factorial(3))));
(6 * (5 * (4 * (3 * factorial(2)))));
(6 * (5 * (4 * (3 * (2 * factorial(1))))));
(6 * (5 * (4 * (3 * (2 * 1)))));
// => 720

Notice that as n increases, n! adds another stack call. This is a linear recursive process. For large values of n, this method uses significantly more space to calculate the same result.

Is your first code example showing really an iterative process? I'm looking at the code closely, imagining it being run... Calling factorial(N) would cause first N recursive iter() calls and then N recursive returns. Would it not? So it would use the stack space proportional to N. Or am I misunderstanding something? — Roman Vinogradov, Jan 21 '16 at 08:43
It uses a tail call, which are only optimized to not grow the stack in ES6. — Gregory Magarshak, May 24 '16 at 01:11

score 2 · Answer 2 · answered Jun 18 '13 at 17:04

I've tried writing about closures before here (no mention of recursion, though):

http://hangar.runway7.net/javascript/guide

But with regards to recursion, I'd say closures can come in to play when recursion happens, but they are not necessarily related. I'd actually recommend that you do not use closures in recursion at all, because that can cause unintended bugs. Recursion often depends on each function call executing with only the knowledge of the arguments explicitly passed in to it, and closures violate this principle.

In practice, closures are a way to share information between functions when defining them, especially when you know that they are going to be executed in unknown contexts.

Recursion, on the other hand, is the process of execution for a function that's structured in such a way that it accomplishes it's job by repeatedly calling itself.

Both concepts can be learned much better by Googling them, but just know that they aren't usually related.

Javascript closures and recursion

2 Answers2

Linked