CODEWITHSUNDEEP
scalarecursionfunctional-programmingfactorial
hispaniccoder
hispaniccoder

Reputation: 397

How does a recursive function return the result in scala?

I am currently learning Scala and I am stuck in the following thing: I have this algorithm which finds in a recursive way the factorial of a number:

 def fact(n:Int): Int=
    { 
        if(n == 1) 1
        else n * fact(n - 1) 
    } 
    println(fact(5))

My question is, why does this line: if(n == 1) 1 does exactly? Does in mean that the function should return one or that n should become 1? I dont understand how this function returns 120 which is the result. Could someone help me udnerstand? I appreciate any help you can provide

Upvotes: 0

Views: 927

Answers (2)

Sagi
Sagi

Reputation: 9294

Lets make this method more c oriented.
Maybe now its more clear that there are two branches
1. When n equals 1 - which stops the recursion. 2. Otherwise - multiply the current value of n by the result of calling the fact method with n - 1, which eventually becomes 1 and stops the recursion.

def fact(n:Int): Int=
{ 
    if (n == 1) {
       (return) 1;
    }
    else {
       (return) n * fact(n - 1);
    }
}

The semicolon is redundant and the the a return keyword is not recommended/necessary.
You can read about it here

So you are left with:

def fact(n:Int): Int=
{ 
    if (n == 1) {
       1
    }
    else {
        n * fact(n - 1)
    }
}

Which is basically the same as:

def fact(n:Int): Int=
{ 
    if (n == 1) 1;
    else n * fact(n - 1)
}

Upvotes: 0

Luis Miguel Mejía Suárez
Luis Miguel Mejía Suárez

Reputation: 22850

Uhm, this is a very broad question.
Since you are asking for basic understanding of the operators of the language. I will try to explain it all to you, but I would recommend you to take a formal introduction to programming course.

In Scala everything is an expression. Thus, the function itself is an expression that evaluates to the assigned block.
In this case the block is just an if / else expression, which takes a predicate to decide which of the two branches to choose. In this case n == 1 checks if n is equals to 1, if that is true, then it returns 1, if not, it returns n * fact(n -1).

Thus, if we execute the algorithm by ourselves using "equational reasoning", we can understand how it works.

fact(3) = if (3 == 1) 1 else 3 * fact(3 - 1) // replace n in the block.
fact(3) = 3 * fact(2) // reduce the if and the subtraction.
fact(3) = 3 * (if (2 == 1) 1 else 2 * fact(2 - 1)) // expand the fact definition.
fact(3) = 3 * (2 * fact(1)) // reduce the if and the subtraction.
fact(3) = 3 * (2 * (if (1 == 1) 1 else 1 * fact(1 - 1))) // expand the fact definition.
fact(3) = 3 * (2 * (1)) // reduce the if.
fact(3) = 6 // reduce the multiplications.

Upvotes: 3

Related Questions