How does a recursive function return the result in scala?

Question

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

No experience with Scala, but from what I know about recursive functions `if(n == 1) 1` should return `1` for `n==1`. It's the terminal condition solving the base case. Any other number will go through the `else` part until it reaches the terminal condition and stops recursing, so `fact(5)` unrolls to `fact(5) * fact(4) * fact(3) * fact(2) * fact(1)` which turns into `5 * 4 * 3 * 2 * 1` and at the list call it stops. — VLAZ, Oct 21 '19 at 17:30
Your question is very unclear. Scala is really no different from pretty much any other programming language when it comes to how a recursive function returns the result. A recursive function is also no different from pretty much any other function when it comes to how it returns the result. So, the answer to your question is basically "just like any other function in any other language". — Jörg W Mittag, Oct 22 '19 at 00:43

score 3 · Accepted Answer · answered Oct 21 '19 at 17:31

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.

score 0 · Answer 2 · answered Oct 21 '19 at 17:38

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)
}

How does a recursive function return the result in scala?

2 Answers2