CODEWITHSUNDEEP
scalarecursiontail-recursiontail
Retrospect
Retrospect

Reputation: 33

What am I doing wrong while translating a Scala Recursion function into a Tail-Recursion function?

I am trying to take this working recursive function (below)...

Problem A description

    def cubeIt(n: Int): Int = {
        println("acc:"+acc);
        println("n: "+n);
        if(n==0){
            return 0;
        }
        else if(n>0){
            return cubeIt(n-1) + 3*(n*n) - 3*n + 1
        }
        else{
            return cubeIt(n+1) - 3*(n*n) - 3*n - 1
        }
    }

...and turn it into a tail-recursion function.

Problem B description

import scala.annotation.tailrec

@tailrec
def cubeItHelper(n: Int, acc: Int): Int = { /* Implement cubeIt as a tail recursion */
    if(n==0){
        return acc;
    }
    if(n>0){
        return cubeItHelper(n-1, acc+(3*(n*n) - 3*n + 1));
    }
    else{
        return cubeItHelper(n+1, (acc+((-3)*(n*n) - 3*n - 1)));

    }
}
/*- 
This is the main function that the users will use. 
It should call the helper with the correct initial value of acc argument. 
Just replace the ??? with the correct initial value for the acc argument.
-*/
def cubeItTail(n: Int): Int = {
    if(n==0){
        return 0;
    }
    else{
        cubeItHelper(n, 0);
    }
}

With the above code it outputs this:

acc:0
n: 5
acc:61
n: 4
acc:98
n: 3
acc:117
n: 2
acc:124
n: 1
......

first four test lines complete correctly

n: -100
acc:-29701
n: -99
acc:-58808
n: -98
acc:-87327
...(goes forever)

These are the test statements (it's hung up on the final one):

assert(cubeItTail(5) == 125)
assert(cubeItTail(-5) == -125)
assert(cubeItTail(-3) == -27)
assert(cubeItTail(0) == 0)
assert( (-100 to 100).forall( x => (cubeItTail(x) == x * x * x)), "Test Passed!")

I'd appreciate it if anyone could tell me what I am doing wrong here.

Upvotes: 2

Views: 209

Answers (2)

Retrospect
Retrospect

Reputation: 33

The print statements

println("acc:"+acc); println("n: "+n);

in the helper function were causing Jupyter Notebook to crash. They may run fully in a different environment, however. Just take note there will be a lot of print statements.

Upvotes: 1

Regan Koopmans
Regan Koopmans

Reputation: 507

The parameter to cubeItTail could be negative, in which case you would need to pass in -1 to cubeItHelper:

def cubeItTail(n: Int): Int = {
    if (n == 0) {
        return 0;
    }
    else if (n > 0) {
        cubeItHelper(n, 1);
    }
    else {
        cubeItHelper(n, -1);
    }
}

Upvotes: 0

Related Questions