12: Q78 – Q80 Recursion in Scala Q&As explained with diagrams

Q. Do functional languages handle recursion better than non-functional ones?

A. Yes because they have to. A pure function is a function with no side effects and no state. Not having side effects means you can’t have loop counters as loop counters as they mutate state, hence it will have a side effect. Recursion is not only a good natural match for pure functional programming, but also having no side effects  makes recursion more efficient as  compiler level optimizations like what order the functions run in, etc can be  carried out .

Q78. What will be the output of the following code? Can you explain why you got this output?

A78. The output is:

The above code makes recursive calls. The recursive call “countUp(input-1)” is made before the “println(input)”. The recursive calls are remembered and gets put into a stack, which is a LIFO (Last In First Out) data structure.

Scala recursion - counting up

Scala recursion – counting up

Q79. Can you write code to insert sort a list of nubers say 5, 4, 3 in ascending order using recursion?
A79.

Output:

//1 recursion is evaluated as
Scala Insert Sort

Scala Insert Sort

POP2 is insert(4, List(3))

Recursion 1:

x <= y is false, hence executes “y :: insert(x, ys) which is “3 :: insert(4, List())”

Recursion 2:

Hence exit condition is reached, and returns List(x) which is List(4). So “3 :: List(4)” is an output of List(3, 4).

POP3 is insert(5, List(3, 4))

Recursion 1:

x <= y is false, hence executes “y :: insert(x, ys) which is “3 :: insert(5, List(4))”

Recursion 2:

x <= y is false, hence executes “y :: insert(x, ys) which is “4 :: insert(5, List())”

Recursion 3:

Now the final result will be from the

recursion 1 => 3 :: insert(5, List(4))

recursion 2 => 3 :: 4 :: insert(5, List())

recursion 3 => 3 :: 4 :: List(5)

Which gives a final sorted result of List(3, 4, 5)

Q80. Can you write code to merge sort a list of nubers say 5, 3, 4 in ascending and descending order using recursion?
A80.

Output:

//1 recursion is evaluated as

1) merge(isTrue)(3) => returns List(3)

2) merge(isTrue)(4) => returns List(4)

3) merge(List(3), List(4)) => x = 3, y = 4, xs = List(), ys = List(). returns List(3, 4) after 2 iterations

4) merge(List(5), List(3, 4)) => after 3 iterations returns List(3, 4, 5)


Categories Menu - Q&As, FAQs & Tutorials

Top