CODEWITHSUNDEEP
javascript
ale
ale

Reputation: 11830

How does this function not use an extra argument

This JavaScript is from Resig's code in his JavaScript Ninja book:

function yell(n){ 
  return n > 0 ? yell(n-1) + "a" : "hiy"; 
} 
assert( yell(4) == "hiyaaaa", "Calling the function by itself comes naturally." );

So it's some simple recursion. I understand recursion. This is probably a dumb question. However, I don't understand why this works in so few lines of code. Where does the "aaaa" get appended to "hiy"? If I was doing this in say Prolog, I think I would have added an extra parameter to yell to keep track of the string being built.

Upvotes: 1

Views: 58

Answers (3)

JLRishe
JLRishe

Reputation: 101710

Let's decompose a call to yell(3):

yell(3) - n > 0 ? yell(2) + "a" : "hiy";
yell(2) - n > 0 ? yell(1) + "a" : "hiy";
yell(1) - n > 0 ? yell(0) + "a" : "hiy";
yell(0) - n > 0 ? yell(-1) + "a" : "hiy";

We can evaluate the conditional expressions:

yell(3) - yell(2) + "a";
yell(2) - yell(1) + "a";
yell(1) - yell(0) + "a";
yell(0) - "hiy";

Then continue to substitute/simplify:

yell(3) - (yell(1) + "a") + "a";          // since yell(2) = yell(1) + "a"

yell(3) - ((yell(0) + "a") + "a") + "a";  // since yell(1) = yell(0) + "a"

yell(3) - (("hiy" + "a") + "a") + "a";    // since yell(0) = "hiy"

And there you have it.

An important reason that this works is that the ?: operator uses short-circuit evaluation and only evaluates the part that is relevant given the outcome of the condition. If it didn't have that, this function would result in infinite recursion.

Upvotes: 2

Olaf Dietsche
Olaf Dietsche

Reputation: 74068

You can rewrite the ternary operator ?: as 

function yell(n) {
    if (n > 0)
        return yell(n - 1) + "a";
    else
        return "hiy";
}

The function calls itself recursively with argument n - 1 until the argument n becomes 0, where it returns hiy. Then recursion is wound up and one a is appended per recursion level.

Upvotes: 0

Wayne
Wayne

Reputation: 60414

This function builds up the string by appending "a" to the return value of the next invocation at each step. It might help to visualize the call stack:

yell(4) = yell(3) + "a"
yell(3) = yell(2) + "a"
yell(2) = yell(1) + "a"
yell(1) = yell(0) + "a"
yell(0) = "hiy"

We now have all the information necessary to see how this works. We just need to "unroll" the stack and plug it back in:

yell(1) = "hiy" + "a"
yell(2) = "hiy" + "a" + "a"
yell(3) = "hiy" + "a" + "a" + "a"
yell(4) = "hiy" + "a" + "a" + "a" + "a"

So the final result is:

"hiyaaaa"

The reason you don't need an additional param is that no stage of the recursion needs access to the value from a previous step. Instead, each value is returning the combination of its value and the next value in the progression.

Upvotes: 2

Related Questions