Link to home
Start Free TrialLog in
Avatar of oggiemc
oggiemcFlag for Ireland

asked on

Function Recursion

Hello all,

Can someone explain the attached code please..And in particular, how the program execution flows between the different scope blocks.. Im not familiar with the way the functions are being called.. Thanks

<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head>
<title>Recursion</title>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<script type="text/javascript">
//<![CDATA[

function runRecursion() {

   var addNumbers = function sumNumbers(numArray,indexVal,resultArray) {
   
      // recursion test
      if (indexVal == numArray.length) 
         return resultArray;

      // perform numeric addition
      resultArray[0] += Number(numArray[indexVal]);

      // perform string concatenation 
      if (resultArray[1].length > 0) { 
         resultArray[1] += " and ";
      }
      resultArray[1] += numArray[indexVal].toString();
   
      // increment index
      indexVal++;

      // call function again, return results
      return sumNumbers(numArray,indexVal,resultArray);
   }

   // create numeric array, and the result array
   var numArray = ['1','35.4','-14','44','0.5'];
   var resultArray = new Array(0,''); // necessary for the initial case

   // call function
   var result = addNumbers(numArray,0, resultArray);

   // output
   document.writeln(result[0] + "<br />");
   document.writeln(result[1]);
}
//]]>
</script>
</head>
<body onload="runRecursion();">

Open in new window

Avatar of cmalakar
cmalakar
Flag of India image

Inside function called runRecursion,

First a function called "sumNumbers" is being defined between lines 10 to 30, and storing its reference in variable called "addNumbers"

After that addNumbers (i.e, sumNumbers) is being called at line 37, which returns the result.

Again with in sumNumbers function, the same function is called till the value of indexVal being passed is equal to the length of the array.
So, it does the sum of all the numbers in array.
Avatar of HonorGod
Execution of the script begins when the page is completly loaded,
and the function identified in the body tag is invoked.

Within runRecursion(), we find an inner function, addNumbers,
which is an alias for sumNumbers.

Variables local to runRecursion() (i.e., numArray, and resultArray)
are initialized, and the inner function addNumbers() is invoked by
the statement:

var result = addNumbers(numArray,0, resultArray);

At this point, what are the values of the parameters?

------------+-------------------------------+
numArray    | ['1','35.4','-14','44','0.5'] |
indexVal    | 0                             |
resultArray | [ 0, '' ]                     |
------------+-------------------------------+

The test (indexVal == numArray.length) is false, so
the value of resultARray[] is modified:

------------+-------------------------------+
numArray    | ['1','35.4','-14','44','0.5'] |
indexVal    | 0                             |
resultArray | [ 1, '1' ]                    |
------------+-------------------------------+

indexVal is incremented, and another call to
sumNumbers is made:

------------+-------------------------------+
numArray    | ['1','35.4','-14','44','0.5'] |
indexVal    | 1                             |
resultArray | [ 1, '1' ]                    |
------------+-------------------------------+

indexVal < numArray.length, so execution continues with
the update of resultArray, and indexVal

------------+-------------------------------+
numArray    | ['1','35.4','-14','44','0.5'] |
indexVal    | 2                             |
resultArray | [ 36.4, '1 and 35.4' ]        |
------------+-------------------------------+

The next call to sumNumbers occurs with these value:

------------+-------------------------------+
numArray    | ['1','35.4','-14','44','0.5'] |
indexVal    | 2                             |
resultArray | [ 36.4, '1 and 35.4' ]        |
------------+-------------------------------+

indexVal < numArray.length, so resultArray, and indexVal
get updated to:

------------+-------------------------------+
numArray    | ['1','35.4','-14','44','0.5'] |
indexVal    | 3                             |
resultArray | [ 22.4, '1 and 35.4 and -14' ]|
------------+-------------------------------+

The next iteration results in:

------------+--------------------------------------+
numArray    | ['1','35.4','-14','44','0.5']        |
indexVal    | 4                                    |
resultArray | [ 66.4, '1 and 35.4 and -14 and 44' ]|
------------+--------------------------------------+

and the next:

------------+----------------------------------------------+
numArray    | ['1','35.4','-14','44','0.5']                |
indexVal    | 5                                            |
resultArray | [ 66.9, '1 and 35.4 and -14 and 44 and 0.5' ]|
------------+----------------------------------------------+

On the next call, indexVal == numArray.length, so the return
is executed, and control returns to the return statement where
sumNumbers() was called, which returns to the statement where
sumNumbers() was called, ...

all the way until the original call to addNumers() was made.

The last statements in runRecursion() are executed to output
the results, and then runRecursion() returns to where the
call was made in the onload call in the body tag.

Hopefully this helps.
ASKER CERTIFIED SOLUTION
Avatar of HonorGod
HonorGod
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of oggiemc

ASKER

HonorGod
Thanks for the comprehensive reply.. Couple of questions though..

1) resultArray[1] += numArray[indexVal].toString();      // Why is toString() method used here?? i.e numArray elements are already of type string

2) return sumNumbers(numArray,indexVal,resultArray);  // On each iteration where are the results "returned"? i.e im not sure why return keyword is used.. why dont you just invoke the function again without the return keyword? i.e sumNumbers(numArray,indexVal,resultArray);  

Thanks again for your help..
Q: Why is toString() method used here?
A: It doesn't have to be, so the result is identical.

Q: On each iteration where are the results "returned"?
A: That is one of the most difficult things to wrap your head around as far as recursion is concerned.

When we a statement like:

  return sumNumbers(numArray,indexVal,resultArray)

We have to remember that the call to sumNumbers() is made, and must exit (return) BEFORE we can finish this return.

Does that make sense?

Each time the statement is executed, a new instance of sumNumbers() "stack" is created with the parameters specified, so that the function can execute independent of previous (suspended) instances.  When this code:


      if (indexVal == numArray.length)
         return resultArray;


Is actually executed, then the unraveling of the nested calls takes place.
Avatar of oggiemc

ASKER

Ok, so am i right in thinking that: when

 if (indexVal == numArray.length)
         return resultArray;


is executed, the return part of

return sumNumbers(numArray,indexVal,resultArray)


is executed??

Thanks for patience
When the

return resultArray

is executed, control returns to where sumNumbers() was called.
So the value (resultArray) that is returne by the

return resultArray

statement will, in turn, be plugged into this statement:

return sumNumbers(numArray,indexVal,resultArray)

where sumNumbers() was called.  So, this statement will effectively act just like the

return resultArray

which provided the value to be returned.

If we had used something like:

result = sumNumbers(numArray,indexVal,resultArray)
return result


instead, it might make a little more sense.  Then it might be more obvious that the result of calling sumNumbers() will be put into the local variable result , which in turn will then be passed back to the statement where this function was called.

Does that help any?

Avatar of oggiemc

ASKER

Ok, i think i get it.. Basically the net effect is that when

return resultArray
is executed, this array is passed to

return sumNumbers(numArray,indexVal,resultArray)
which in turn is returned to

var result = addNumbers(numArray,0, resultArray);
i.e the result array is assigned to result..

Hope im right! Have never come across this technique before..
yes.  Remember though, that each instance of:

return sumNumbers(numArray,indexVal,resultArray)

creates a "place holder" for the result of the function call.
Generally this is implemented as a stack, so that each
execution of the actual "return" operation, will "pop the stack"
and return the result to the function call.

So, our example from above might be represented as shown below.

Each indentation is used to represent a nested call to the function.
When the final (deepest) function actually executes the return
operation with an actual value, then the stack starts unwrapping.

Does this help?
var result = addNumbers( numArray, 0, resultArray )
  > ...
    return sumNumbers( numArray, 1, resultArray )
    > ...
      return sumNumbers( numArray, 2, resultArray )
      > ...
        return sumNumbers( numArray, 3, resultArray )
        > ...
          return sumNumbers( numArray, 4, resultArray )

Open in new window

Thanks for the grade and points.

Good luck & have a great day.
Avatar of oggiemc

ASKER

thank you good sir for help!