CODEWITHSUNDEEP
javascriptrecursion
devdropper87
devdropper87

Reputation: 4187

all anagrams - recursion

I'm trying to understand the following recursive function below to teach myself recursion. My attempt to explain it is below the expected output and the function itself. what am I missing? I'm not seeing the process where you get from 'abc' to 'acb'. my attempt to understand it got me from 'abc' right to 'bac'.

    example usage:
        var anagrams = allAnagrams('abc');
        console.log(anagrams); // [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]





        var allAnagrams = function(string) {

          var uniqueOutput = {};

          (function anagram(ana, str) {

            // could have also written this as: if(!str)....
            if (str === '') {
              uniqueOutput[ana] = 1;
            }
            //recursive call for the length of the anagram.
            for (var i = 0; i < str.length; i++) {
              anagram(ana + str[i], str.slice(0, i) + str.slice(i + 1));
              console.log(ana);
            }
          })('', string);
          console.log(uniqueOutput)
          return Object.keys(uniqueOutput);
        };


 // you are calling the recursive function like this: anagram([anagram=]'', [string=]'abc')
    // so the base case is not met on the first iteration since the string isn't empty
    // first iteration: i = 0
    // anagram('' + 'a' + 'bc' [from str.slice(0 +1)]) ---> resolves to "abc") ---> anagram("abc")
    //second iteration: i = 1. we are still in the original call from line 37.
    // here below, does "ana" stay as '' since we are still inside the initial recursion call?
    //anagram('' + b + a +  c) ---- resolves to "bac" ---> anagram("bac")
    //third and last iteration iteration: i = 2
    //anagram(" " + c + c) ----> anagram("cc") ? not a valid result.

My new, correct (I think) explanation:

//initial input: anagram("", "abc")
//STEP 1: enter the function --> i = 0 for original string "abc"
  //anagram("" + "a", "bc") ----> anagram("a", "bc")
//STEP 2: loop through the new, modified string, which is now "bc"
    //var i = 0;
    //anagram("a" + "b", "c")---> anagram("ab", "c")
    //anagram("ab" + "c", [nothing here])
      //base case hit, so uniqueOutput["abc"] = 1;
    //var i = 1; --> this applies to the string "bc". the loop gets reset to i = 0 once you have a new string to worth with (like below, with "b")
    //anagram("a" + "c", "b")
    //anagram("ac", "b")
    //anagram("ac" + "b", "" )
      //base case hit, so uniqueOutput["acb"] = 1;  
//STEP 3: increment up on the original string input ("abc") --> so now you are dealing with str[i] === b
  //var i =  1;
  //anagram("" + "b", "a" + "c")
    //anagram("b", "ac")  ---> now we need to loop through "ac"!
      //anagram("b" + "a", "c")
        //anagram("ba", "c") 
          //anagram("bac", "")---> base case hit, uniqueOutput["bac"] = 1;
    //anagram("b", "ac")
      //anagram("b" + "c", "a") ---> anagram("bc", "a")
        //anagram("bca", "") ---> base case hit, uniqueOutput["bca"] = 1;
//STEP 4: increment up on the original string input ("abc") ---> str[i] === c
  //var i = 2;
  //anagram ("" + "c", "ab")---> anagram("c", "ab")
    //now we need to loop through "ab!" c's index stays the same.
    //anagram("c" + "a", "b") ---> anagram("ca", "b")
      //anagram("cab", '')---> uniqueOuput["cab"] = 1;
    //anagram("c" + "b", "a") ---> anagram("cb", "a")
      //anagram("cba", "")----> uniqueOutput["cba"] = 1

Upvotes: 2

Views: 2433

Answers (2)

rahpuser
rahpuser

Reputation: 1249

You are missing the second iteration.. this is the execution flow in comments:

    // anagram('', 'abc') level 0
      // condition false... level 0
      // first iteration: i = 0  level 0
      // anagram(a', 'bc') ( creating new execution context level 1 )
        //  condition false.. level 1
        //  iteration 1... level 1
        // anagram('ab', 'c') ( creating new execution context level 2 )
          //  condition false..  level 2
          //  iteration 1... level 2
          // anagram('abc', '') ( creating new execution context level 3 )
            // condition true.. push "abc"
          // end for of level 2 context execution
        // iteration 2...  level 1
        // anagram('ac', 'b') ( creating new execution context level 2 )
          //  condition false.. level 2
          //  iteration 1... level 2
          // anagram('acb', '') ( creating new execution context level 3 )
            // condition true.. push "abc" level 3
          // end for of level 2 execution
        // end for of level 1
      // second iteration of level 0....
      // keep this pattern till end for of level 0..
    // end anagram level 0

As you can see, each iteration of the level 0 is going to push 2 words to the object. If we follow your logic, each iteration is pushing just one, take into consideration that recursion is just like adding more code in that exact place, once the function call finishes the execution flow returns to the place where it was before the call of the function.

Upvotes: 2

sheilak
sheilak

Reputation: 5873

From your comments above:

// first iteration: i = 0
// anagram('' + 'a' + 'bc' [from str.slice(0 +1)]) ---> resolves to "abc") --->

Actually on i = 0, the arguments passed to anagram are:

anagram('' + 'a', '' + 'bc');

which evaluates to:

anagram('a', 'bc');

Then within that call to anagram, we again loop over str, which is now just 'bc'. That will result in 2 more calls to anagram which will be

anagram('a' + 'b', '' + 'c'); // i = 0
anagram('a' + 'c', 'b' + ''); // i = 1

which evaluate to:

anagram('ab', 'c');
anagram('ac', 'b');

And the second one of those calls will result in another call to anagram with these arguments:

anagram('acb', '');

which gets added to uniqueOutput as str is now empty.

Only after all that has executed will the code return to the outermost call of anagram and i will increment as per your comment:

//second iteration: i = 1. we are still in the original call from line 37.

Upvotes: 3

Related Questions