Scala recursive function

Question

object MainObject {  
   def main(args: Array[String]) {  
        var result = recur(15,2)  
        print(result)  
    }  
    def recur(a:Int,b:Int):Int={
        if(b==0)
        0
        else
        a+recur(a,b-1)
    }
}

in this above code, can somebody explain to me how step by step this gets executed?

Please correct me if I am wrong: after else there is recur function does this call recur(15,2) in each iteration? By deducting on each time? If yes then at 3rd run b will be 0, so why it doesn't return 0 as that if becomes true.

Naveen, if one of the solutions below solves the problem/question for you, can you please indicate this by checking the corresponding green checkmark? Thanks! — Max von Hippel
– Max von Hippel, Commented May 31, 2018 at 16:20

Ahmad Ragab · Accepted Answer · 2018-05-31 15:54:07Z

3

A couple of comments.

1) Since the value of result is only assigned once it would be more idiomatic, and generally preferable to use val instead of var.

val vs var in Scala

2) Also, in Scala you can define functions inside functions, this is often useful when you don't want to expose the behavior of the recursion to the larger context.

3) Consider outside-in evaluation:

recur(15, 2) returns 15 + recur(15, 1)
recur(15, 1) returns 15 + recur(15, 0)
recur(15, 0) returns 0

Now substitute:

recur(15, 1) returns 15 + 0
recur(15, 2) returns 15 + 15 or 30

answered May 31, 2018 at 15:54

Ahmad Ragab

1,1171 gold badge12 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mureinik · Accepted Answer · 2018-05-31 16:02:10Z

1

The best way to visualize this, IMHO, is to follow the execution "from the outside in":

First, we call recur(15, 2), which will return 15 + recur(15, 1)
Now, let's evaluate recur(15, 1) - it will return 15 + recur(15, 0).
Now, we should evaluate recur(15, 0), which, as you mentioned, will return 0.
If so, the result of step 2 is 15+0, or 15.
If so, the result of step 1 is 15+15, or 30.

edited May 31, 2018 at 16:02

answered May 31, 2018 at 15:45

Mureinik

316k54 gold badges398 silver badges405 bronze badges

2 Comments

Ahmad Ragab Over a year ago

I think in step four you mean "the result of step 2 is 15 + 0" since recur(15,0) returns zero as you rightly claim. The answer I am reasonably sure should be 30 not 45.

Mureinik Over a year ago

@AhmadRagab yup, momentary lapse of concentration on my part, edited and fixed.

James Whiteley · Accepted Answer · 2018-05-31 15:56:52Z

An easy way to look at this one is to ascribe values to each stage of the calculation, and calculate is backwards:

For each step, the second parameter is reduced by 1 and the first stays the same.
At b = 0, the output is 0.
recur(15, 2) = 15 + recur(15, 1)
recur(15, 1) = 15 + recur(15, 0)
recur(15, 0) = 0

We know that recur(15, 0) = 0
recur(15, 1) == 15 + recur(15, 0) == 15 + 0 == 15

And because recur(15, 1) = 15
recur(15, 2) == 15 + recur(15, 1) == 15 + 15 == 30

So the answer to recur(15, 2) is 30. Going backwards like this is very helpful for simpler functions but can get very complex so writing it out like I have or jotting down the output at each stage so you don't lose track of your calculations.

... or get a compiler to do it. Either works.

Collectives™ on Stack Overflow

Scala recursive function

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related