return 1 2

[slobad23]

I have got this example of a recursive function:

<code>
function power(base, exponent) {
if (exponent == 0) {
return 1;
}
else
{
return base * power(base, exponent - 1);
}
}

alert(power(2, 10));
</code>

I would have thought that the result (which equates to 1024) would need to be stored in a variable inside the function and that value returned for the alert to use.

As it is, the function returns the calculation with return 1 (return true also works).

I was hoping someone could explain how this value is stored throughout the function and how "return true" is able to provide the caller (alert), with this value.

 

[vacunita]

It doesn't. Return 1 mainly ends the function in the event the exponent is 0. Which is a default calculation.
And ends the recurssion when there are no more exponents.

The real action takes place below in return base* power(...) Which simply returns the result of multiplying the base times the result of your function.



----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

 

[feherke]

Hi

Sounds like you have a basic problem with understanding recursion. I suggest to read the Recursion (computer science) article in Wikipedia first.

Your recursion question has nothing to do with JavaScript. Recursive functions work the same way in all languages.

I am not good in explaining things, so I try to "draw" it instead to show how the calculation is done :

[small]
call        [gray]|[/gray] exponent [gray]|[/gray] exponent == 0 [gray]|[/gray] return
[gray]------+----------+---------------+--------------------[/gray]
power(2, 3) [gray]|[/gray] 3        [gray]|[/gray] false         [gray]|[/gray] [highlight #fcc]2[/highlight] * power(2, 3 - 1)
                                         [red]\_______[/red][silver]/[/silver][red]_________/[/red]
       [silver]_________________________________________/[/silver]  [red]\_________________________[/red]
      [silver]/[/silver]                                                                    [red]/ \[/red]
power(2, 2) [gray]|[/gray] 2        [gray]|[/gray] false         [gray]|[/gray] [highlight #cfc]2[/highlight] * power(2, 2 - 1)              [red]/   \[/red]
                                         [green]\_______[/green][silver]/[/silver][green]_________/[/green]             [red]/     \[/red]
       [silver]_________________________________________/[/silver]  [green]\___________________________[/green] [red]\[/red]
      [silver]/[/silver]                                                                [red]/[/red]     [green]/ \[/green] [red]\[/red]
power(2, 1) [gray]|[/gray] 1        [gray]|[/gray] false         [gray]|[/gray] [highlight #ccf]2[/highlight] * power(2, 1 - 1)          [red]/[/red]     [green]/   \[/green] [red]\[/red]
                                         [blue]\_______[/blue][silver]/[/silver][blue]_________/[/blue]         [red]/[/red]     [green]/     \[/green] [red]\[/red]
       [silver]_________________________________________/[/silver]  [blue]\_____________________________[/blue] [green]\[/green] [red]\[/red]
      [silver]/[/silver]                                                            [red]/[/red]     [green]/[/green]     [blue]/ \[/blue] [green]\[/green] [red]\[/red]
power(2, 0) [gray]|[/gray] 0        [gray]|[/gray] true          [gray]|[/gray] [highlight #fcf]1[/highlight]                        [red]/[/red]     [green]/[/green]     [blue]/   \[/blue] [green]\[/green] [red]\[/red]
                                         [purple]\________________________________________[/purple] [blue]\[/blue] [green]\[/green] [red]\[/red]
                                                                [red]/[/red]     [green]/[/green]     [blue]/[/blue]     [purple]|[/purple] [blue]\[/blue] [green]\[/green] [red]\[/red]
                                                                [highlight #fcc]2[/highlight] * ( [highlight #cfc]2[/highlight] * ( [highlight #ccf]2[/highlight] * ( [highlight #fcf]1[/highlight] ) ) )
[/small]

Feherke.

 

[slobad23]

So "return 1" or "return true" breaks out of the if statement and the function. Where is the value 1024 being stored to give that value back to alert?

The recursive function is saying do *this*, over and over until exponent is 0, then stop and return true. How is the alert given a result of 1024 to pop up?

 

[vacunita]

It ends the recursion, so the function doesn't continue to call itself forever. true evaluates to 1 for all intents and purposes and that's what it returns 1.

How is the alert given a result of 1024 to pop up?

Because the function automatically returns the result of multiplying base times the result of next call to itself

For 2 to the tenth power it will do this 10 times.

It doesn't store the result anywhere, it immediately returns it to the calling function whether it be itself or the alert function..

At then what it does is it recurrs itself "exponent" number of times after the initial call. Once it reaches the end. It then calculates back based on the values each call to the itself is returning.

As an example lets do this 2 to 3rd power. That would be 8.

The function enters the first time as called by the alert

alert(power(2, 3));

base = 2, exponent = [red]3[/red]
exponent is not equal to 0, it moves on.

[ ... return base * power(base,exponent - 1 ); ... ]
return 2 * power(2,[red]3[/red]-1) [green]<-"Call number 2 to power"[/green]

then

base = 2  exponent = [red]2[/red] (3 - 1 )
exponent is not equal to 0 it moves on
[ ... return base * power(base,exponent - 1 ); ... ]
return 2 * power(2,[red]2[/red]-1) [green]<-"Call number 3 to power"[/green]

then

base = 2  exponent = [red]1[/red] (2 - 1 )
exponent is not equal to 0 it moves on
[ ... return base * power(base,exponent - 1 ); ... ]
return 2 * power(2,[red]1[/red]-1) [green]<-"Call number 4 to power"[/green]

then

base = 2  exponent = [red]0[/red] (1 - 1 )
exponent is  equal to 0 it returns 1

The 1 is used in the third call to power to evaluate base * power(base,exponent - 1 ) : base * 1 : 2 * 1 = 2

So 2 is used in the second call to power to evaluate again base * power(base,exponent - 1 ) : 2 * 2 = 4

So 4 is used in the inital call to power to evaluate again base * power(base,exponent - 1 ): 2 * 4 = 8

8 is returned by the function to the alert.





----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech

 

[slobad23]

So the whole recursive function stacks on top of each other, is that what you are saying above?

Do this (1)
Do this (2)
Do this (3)
Try to do this... return 1 (stop)

Stack now looks like this:

(stop)
(3)
(2)
(1)
alert the value given once the above stack has been resolved, top to bottom?

 

[slobad23]

I UNDERSTAND.

Got it.

Thank you all so much for you help! I will star the 2 posts:

Feherke
&
Phil AKA Vacunita

Those two posts together really pieced it together.

Thank you very much, trying to figure that out was driving me crazy!

 

[vacunita]

Yes, that's exactly what it does.

Glad we could help.



----------------------------------
Phil AKA Vacunita
----------------------------------
Ignorance is not necessarily Bliss, case in point:
Unknown has caused an Unknown Error on Unknown and must be shutdown to prevent damage to Unknown.

Web & Tech