CODEWITHSUNDEEP
scalarecursion
user568109
user568109

Reputation: 47993

Why this recursive function won't work

I have this function to calculate x to the power of n recursively:

def pow(x:Double,n:Int):Double={
    if (n==0) 1
    else if (n<0) 1/pow(x,-n)
    else if (n%2 == 1) x*pow(x,n-1)
    else pow(pow(x,n/2),2)
}

But this won't work for the last case properly (i.e. positive even numbers). It just hangs there. However if I give this:

def pow(x:Double,n:Int):Double={
    if (n==0) 1
    else if (n<0) 1/pow(x,-n)
    else if (n%2 == 1) x*pow(x,n-1)
    else {val y=pow(x,n/2); y*y}
}

It runs as expected. Can anyone tell me what makes the first implementation wrong. I am attempting to answer Question 10 from Chapter 2 of the book Scala For Impatient.

Upvotes: 2

Views: 170

Answers (2)

user908853
user908853

Reputation:

With your method at some point you end up doing:

pow(pow(x,1),2) -> pow(x*pow(x,0),2) -> pow(x,2) -> pow(pow(x,1),2) -> ...

This is because n==2 is only handled by the last condition which ends up calling itself over and over again...

Upvotes: 3

Rex Kerr
Rex Kerr

Reputation: 167871

You always call pow(...,2) in the last case, and the last case is the only one that handles n==2. So....

Upvotes: 2

Related Questions