Scala recursion explanation from Scala book

Question

I was going through scala book by Martin Odersky. In chapter10(Composition and Inheritance), in this code:

def spiral(nEdges: Int, direction: Int): Element = { if (nEdges == 1) { elem("+") } else { println(s"nEdgesInside1=$nEdges") val sp = spiral(nEdges - 1, (direction + 3) % 4) def verticalBar = elem('|', 1, sp.height) def horizontalBar = elem('-', sp.width, 1) println(s"nEdgesInside2=$nEdges") if (direction == 0) (corner beside horizontalBar) above (sp beside space) else if (direction == 1) (sp above space) beside (corner above verticalBar) else if (direction == 2) (space beside sp) above (horizontalBar beside corner) else (verticalBar above corner) beside (space above sp) } }

I am unable to understand how code flows beyond the line:

val sp = spiral(nEdges - 1, (direction + 3) % 4)

Accoording to my understanding, nEdges is getting decremented in every iteration spiral function is called and once it reaches 1(i.e termination condition) it creates object via elem function.

When I test this code and print the values of nEdges, it gets decremented till the line above call of spiral function and after that line it starts to increment. Could anyone explain me how this is happening.

Thanks in advance

Yuval Itzchakov · Accepted Answer · 2017-08-13 15:44:09Z

This is basically how recursion works. edges gets decremented until it reaches 1, and while doing that it keeps calling spiral which generates more stack frames, each with it's own value of nEdges and direction. Once we hit 1, the call stack starts to unwind, older stack frames get destroyed, which means lesser values of these two fields get discarded in place of values higher up the stackframe, where they have a higher value.

For example, take this image of a recursive factorial calculation:

Imagine that n stands for nEdges, you see that it's decremented with each method call, and when n = 0, we start unwinding and go higher and higher up the stack where n had a higher value.

Collectives™ on Stack Overflow

Scala recursion explanation from Scala book

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related