Using two functions in a recursion Javascript

Question

I'm trying to understand how this code creates the array combinations I'm looking for but I'm not clear on how passing the same function a second time line 6 in a recursion works. I've been working on my understanding of recursions, but I'm not sure how passing the function again for the 2nd time does. Any clarification on this would be helpful.

function string_recurse(active, rest) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length));
        string_recurse(active, rest.substring(1, rest.length));
    }
}
string_recurse("", "abc");

It's not really clear what exactly you want to know. We don't know where you got that function and why you need it to work the way it works, so what kind of answer do you expect? The function calls itself recursively and it does so twice in a call - but as for the why, only the original author can tell you. — Constantin Groß, Feb 12 '17 at 00:35
See [Permutations without recursive function call](http://stackoverflow.com/questions/34013675/permutations-without-recursive-function-call) — guest271314, Feb 12 '17 at 00:58

rpadovani · Accepted Answer · 2017-02-12T00:51:43.063

Each time it ends a recursion, (so it reaches the if (rest.length == 0)) it goes back to the caller. The caller instead of going to back to its own caller (as is usual) calls the recursion again.

Take a look to the example with a bunch of console.log that can explain things

function string_recurse(active, rest, i) {
    if (rest.length == 0) {
        console.log(active);
    } else {
        console.log('Calling 1st recursion at depth', i);
        string_recurse(active + rest.charAt(0), rest.substring(1, rest.length), i + 1);
        console.log('Ended first recursion, calling second one at depth', i);
        string_recurse(active, rest.substring(1, rest.length), i + 1);
        console.log('Ended second recursion at depth', i);
    }
}
string_recurse("", "abc", 0);

Or, if it is better, here a schema that tries to explain the sequence in the call:

f("", "abc")
|
|
--- f("a", "bc")
    | 
    |
    --- f("ab", "c")
        |
        |
        --- f("abc", "") -> console.log()
        --- f("ab", "") -> console.log()
    |
    |
    --- f("a", "c") 
        |
        | 
        --- f("ac", "") -> console.log()
        --- f("a", "") -> console.log()
|
|
--- f("", "bc")
    |
    |
    --- f("b", "c")
        |
        |
        --- f("bc", "") -> console.log()
        --- f("b", "") -> console.log()
    |
    |
    --- f("c", "") -> console.log()

You can see from the start to the end the order of the calls, and you can see every function or has two children or print the value of active

score 0 · Answer 2 · answered Feb 12 '17 at 00:45

Run this snippet, it might help you visualize it:

 var h = 0;
 var i = 0;
 var j = 0;

 function string_recurse(active, rest, x) {
     h += x==='a' ? 1 : 0;
     i += x==='b' ? 1 : 0;
     j += x==='c' ? 1 : 0;
     console.log(`${x} (a${h} b${i} c${j}) active:${active}`);
     if (rest.length == 0) {
         //console.log(active);
     } else {
         string_recurse(active + rest.charAt(0), rest.substring(1, rest.length), "b");
         string_recurse(active, rest.substring(1, rest.length), "c");
     }
 }
 string_recurse("", "abc", "a");

Console:

a (a1 b0 c0) active:
b (a1 b1 c0) active:a
b (a1 b2 c0) active:ab
b (a1 b3 c0) active:abc
c (a1 b3 c1) active:ab
c (a1 b3 c2) active:a
b (a1 b4 c2) active:ac
c (a1 b4 c3) active:a
c (a1 b4 c4) active:
b (a1 b5 c4) active:b
b (a1 b6 c4) active:bc
c (a1 b6 c5) active:b
c (a1 b6 c6) active:
b (a1 b7 c6) active:c
c (a1 b7 c7) active:

Using two functions in a recursion Javascript

2 Answers2