Hi, everyone!
I’m a university student and have been learning Scala for two weeks. While I’m still getting familiar with it, I’d like to ask for your advice.
-
Managing Recursive Code: While Scala allows for compact and elegant code, I sometimes struggle with recursion, as it can be harder for me to understand. I know that breaking the problem down (Divide and Conquer) can help, but I often find merging the partial solutions more challenging, particularly when the codebase grows large and complex. What are some effective ways to manage and simplify recursive algorithms in Scala when dealing with more extensive code?
-
Optimizing Recursive Functions: What strategies or best practices would you recommend for optimizing recursion in Scala, ensuring both readability and performance?
I realize these questions are more conceptual than code-specific, but my goal is to deepen my understanding of Scala. Any advice for a beginner would be greatly appreciated!
Thanks in advance!
2 Likes
Welcome to the Scala community, @ITOWFYL 
Both of these subjects are covered in the first two online courses in the Scala specialization (Functional Programming and Functional Program Design).
For 2, Scala has the @scala.annotation.tailrec annotation you can place before a recursive function. It forces the Scala compiler to verify that the function is tail-recursive. This way you won’t get stack overflows. Scala is limited in tail recursion optimization due to the Java Virtual Machine; the compiler can only tail-optimize simple functions that call themselves directly (so, no mutual recursion stuff). With or without @annotation.tailrec the compiler will replace it with a much more efficient while loop in the generated code, IF the code is correctly tail-recursive. This is covered in the first online course, Week 1:
1 is a much more general problem and not related to Scala. The issue is most likely with your problem solving skills. The general, vague (and fairly useless) advice people often give is: “learn how to break a problem down”. But people don’t know how to do that, or to put it back together. Problem decomposition and re-composition is not taught anywhere.
There isn’t a simple solution to this; this skill is built up slowly over years, especially in math courses. I’d recommend taking those first two online courses, they have some hard problems with large recursive code bases (especially the Water Pouring and Bloxorz problems in the second course). Be prepared to get stuck and frustrated! 
Also start Susanna Epp’s Discrete math book if you have time. After that you can advance to Tim Roughgarden’s Algorithms Illuminated books where he tackles much bigger recursive problems in great detail and breakdown. There is actually a theoretical, structured way to “put partial solutions back together” covered in his books, but it takes a lot of time to learn. (Can’t just explain it here)
Hope it helps. Feel free to reach me if you have questions. 
5 Likes
@ITOWFYL
This is topical for me, as I’ve been wrestling with this sort of thing in Kinetic Merge.
To fix that problem, I tried doing some experiments using generation of Fibonacci numbers as a toy problem.
So in answer to your second question:
I’ve bundled up the toy problem into a Scastie: Scastie - An interactive playground for Scala.
Hope it’s useful to you. I’m not saying that you’ll want to directly jump into all the techniques there, but you’ll get an idea of what’s out there.
Back to your first question:
@spamegg1 pretty much said it all, but to reiterate:
This is very much dependent on the specifics of what you want to do. Try studying some classic computer science algorithms that use divide-and-conquer to see how they both break down and build up the solutions, you’ll get a feel for it.
Quicksort is good for decomposition, mergesort gives you a slighly more complex building of the solution from subproblem solutions.
Maybe try a book that approaches this for Java or C, and see if you can convert the usually imperative code into a functional approach for practice.
4 Likes
Small tangent, but worth noting if you’re still getting into this stuff: while recursion is conceptually important, and worth getting the hang of, keep in mind that most applications only use recursion per se occasionally.
It gets easier with practice, but recursion is always a bit boilerplatey, and requires a little extra thought. (Not least, remembering to add the afore-mentioned @tailrec marker when appropriate.)
Most of the operations you could handle with recursion have higher-order functions already existing (either in the standard library or in Cats), which are usually easier to use. My rule of thumb is:
- 95% of the time, there’s a function that deals with exactly the problem at hand. (Heck,
map() alone might account for 95%.)
- 95% of the remainder can be handled with
fold().
- The remaining fraction of the time is when you actually need recursion.
In practice, I reach for a homebrew recursive solution maybe a few times a year nowadays, usually for weird inner loops. It’s crucial when I need it, but that’s not often.
All that said, the mode of thought is well worth learning. All of these approaches are about learning to break down the problem into the right bite-size steps; which pattern you use to implement that is arguably less important.
6 Likes
Procrastinating from what I should be working on, after reading Nanotrusting the Nanotime, I thought I’d do some JMH benchmarking of the examples in the Scastie. Inputs to each run are (0 to 20) :+ 46:
[info] Benchmark Mode Cnt Score Error Units
[info] FibonacciBenchmarks.naive thrpt 25 0.065 ± 0.001 ops/s
[info] FibonacciBenchmarks.imperativeCache thrpt 25 229157.909 ± 11189.906 ops/s
[info] FibonacciBenchmarks.fpPlod thrpt 25 40668.012 ± 968.564 ops/s
[info] FibonacciBenchmarks.stateTransformer thrpt 25 3958.142 ± 86.551 ops/s
[info] FibonacciBenchmarks.justEval thrpt 25 30242.369 ± 270.806 ops/s
[info] FibonacciBenchmarks.noForking thrpt 25 450575.947 ± 15259.865 ops/s
[info] FibonacciBenchmarks.tailRecursion thrpt 25 479004.995 ± 28571.721 ops/s
3 Likes
That’s some hardcore productive procrastination 
2 Likes
@ITOWFYL There is a nice example of Quicksort in the deck posted here: From Subtype Polymorphism To Typeclass-based Ad hoc Polymorphism - An Example.
That deck goes over and above what you’re asking about, but the starting example is worth a look, and the subject of that deck is worth revisiting once you’ve become more comfortable with Scala.
I would imagine that having a look round FPIlluminated might be useful anyway…
3 Likes
