I’m trying to learn Julia on examples.
For now I’m trying to solve some problem with DFS as a core algorithm in my solution. This recursive DFS is running on a max 1000×1000 grid and I’ve got StackOverFlow (I’m pretty sure it is not the case of a bug in DFS itself).
I found some articles, where explaned that Julia is just bad in recursion.
Is that true and Julia is wrong tool for such tasks? I know that there is recursion-free variant for DFS using stack (may be I will implement it too).
btw, is there any good intro to the best practice where/how to use Julia?
Many thanks!
It’s not so much that Julia is the wrong tool, but that recursion in Julia is the wrong tool. You can always rewrite your recursion by pushing and popping from a stack, and you know better than the compiler what data you care about. With the recursive solution, the compiler needs to keep around a bunch of extra information about what functions were called in order for return to go to the right place.
Hi @rgu, welcome aboard!
Julia can do recursion without major issue, the trouble (as you noted) is the stack depth. A DFS on a 1000x1000 grid means you might have as many as 1 000 000 stacked recursive calls, which is a lot. I would definitely recommend you switch to a loop-based implementation (or borrow one from Graphs.jl using GridGraphs.jl, if that is appropriate for your problem?).
As for resources on “best Julia practices”, not sure what you expect, can you clarify? Do you want some form of decision chart on when to use Python vs Julia for instance? Cause that is hard to provide, and it depends a lot on personal preferences. If you tell us more about yourself or your problem(s) we might be able to help
To be honest, I think that blog post makes a terrible job of explaining why Julia would struggle with recursion, and to compare its limitations to other languages (what is Slowsort? where is its code in both languages? why define a depth of recursion before failure metric and just use it for Julia?).
The stack limitation exists for any languages, just some languages are better at reorganizing some specific kinds of recursion (not all types of recursion are automatically optimized) into the loop with manually managed stack that you can always code yourself.
If you are thinking about using Julia to implement recursive algorithms, forget it. It just won’t work properly, well not unless you have some idea what the depth of recursion will be… but that’s hardly the point of recursion.
This is a valid comment for all languages, I do not understand why to single out Julia here.
On the contrary, I think recursion is a great tool and use it often in Julia; of course, it has its limits, but no more so than in most other performance-oriented imperative languages (e.g. C).
But you have to use recursion appropriately. If you are recursing thousands of times in an imperative language, you should probably consider a loop (perhaps with an explicit stack/queue data structure). If each recursive call is extremely cheap, then you should consider “coarsening” your recursion (e.g. by enlarging the base case) to amortize the function-call overhead (this is true in any language, BTW, at least for non-tail calls). See also the discussion here: Recursive call vs while loop - #18 by stevengj
I think it’s a common myth that recursion is necessarily slow. The key trick that is usually missing from such discussions is to enlarge the base case.
Yes, I routinely interact with people who’ve hit recursion depth limits in Python. This is just something people eventually need to learn to handle in whatever language they use.
Well, I try to expand. I am a teacher in high school, quite clever kids of age about 13-17.
We use Python and C++.
Python — as a wide-range tool (to be able to write standard algorithms like sorting or Eratosphenes sieve as well as some image processing, ML, etc)
Kids who want to write more effective (fast) programs and participate in competitive programming contests use C++.
May be I am speaking of stereotypes, but usually we wouldn’t use C++ or Fortran for UI or Python for low-level system utilities.
I’ve read some materials on statistics with R and Julia and want to refresh my language base. So started Julia and try to implement different tasks using it (and thereby learn the basics). From other point of view — it is important for me to understand what is good task for Julia and what is not. For example, is that good idea to implement compression using Huffmann code or cryptographic protocol (RSA) or computational geometry to learn core 3d-graphics. I believe there are proper libraries in Julia to do all this stuff. Idea is to do this ourselves to know how-it-works.
Comparing Julia vs Python (I’m afraid because started Julia week ago)… it seems Julia needs a bit more qualification from programmer and doesn’t provide simple workaround without real understanding of what you do. But “it’s not a bug it’s a feature”, of course.
Exactly the same — it is standard error I see in students code when they got Run-Time with clear DFS and I know that setrecursionlimit is a common practice here.
I just realized that in Julia workaround is to use stack instead. That is much harder task (for students) but it is honest at least, I agree.
I think at the high school level, whatever you want to do in Python you can do in Julia, and vice versa. Their syntax is very similar, and all the bases are covered on either side. In my opinion, Julia might actually be a nice language for learning programming, since you can poke around as deep as you want to understand stuff.
As far as speed is concerned, Julia can rival C++ in many cases, but it takes some work to get it there. However, I would argue the amount of work needed is much less than learning C++, so it may be a good choice for competitive programming as well! Take a look at Which programming language is fastest? (Benchmarks Game) for instance
I think Juila is a very interesting language for teaching programming. Python of course gives you, with the libraries, the easiest path for students to code anything and produce something pretty. But if your students have already the prospect of using low level languages for anything, they are interested in really learning programming. In that case, Julia is a good fit, because it can expose to the user many fundamental concepts that python will mostly hide. In terms of performance, basically the students have to learn that querying new memory addresses and slots to the system is slow. Most performance tips of Julia derive from that: preallocate memory, avoid intermediates, avoid type instability (which imply boxing and, thus allocations), avoid dynamic dispatch.
Also with Julia they learn what compilation means (which python also hides), learns what code specialization is, can easily play with different number representations in simple computations and check for the performance.
We have students (at the university) that, on the contrary have been so much influenced by the python way of thinking that one needs to break a learning barrier to introduce the concepts that are necessary for performance programming, in any language. Everything just seem magical.
To add on this:
Learning recursion without hitting the stack limit is NOT learning recursion.
Learning about algorithms and programming techniques should include the underlying principles of how processors and memory management work. Recursion and the stack is an example on why this is important. Another examples: Integer operations and overflow, float operations and precision, there are many more.
Even if modern software development doesn’t need to use registers and memory addresses anymore, it is good for a general understanding of software, to know what’s going on in the CPU and in the memory. Basic data types for example do have a correspondence in the memory architecture of the machines. This makes it easier to understand why there is something like an Int64. The binary representation of numbers in computers, as an extreme example, is not a mandatory knowledge for many programming tasks, but it should be definitely known, as, I guess, many would agree.
Therefor: Julia is perfect for learning recursion. Next level: perfect for learning how to do the same in loops. Next level: perfect to learn about tail recursion and it’s optimization.
That would bring the principles into relation to each other and in relation to the hardware. Those relations makes it easier(!) to learn, comprehend and remember them.
Recursion is not an efficient way to implement DFS no matter what language you use. This is not a Julia issue. It’s an issue with implementing DFS with recursion in general.
That being said, functional programmers may have some tricks to resolve this issue. For Julia, it is best to just turn to stack.
I solved some Project Euler stuff using Scheme, and started to like tail recursion, so when I found out that Julia doesn’t (yet?) support tail recursion, I was a little bummed. Mind you, I wasn’t bummed because lack of TCO was hurting my ability to work, or that I had run into a limit somewhere … I just missed it.
I think I just got allergic to for loops, and tried to solve everything in a Scheme-y way in any language that would allow it. Julia is the first (non-C) language I have used on a regular basis where for loops are not a bad idea.
Edit, and unrelated, but Project Euler is a lot of fun. I might try it again with Julia.
For recursion in programming, yes, I do agree. For recursion in mathematics, of course not. If I was a Maths teacher just using a language to exemplify some concepts, I would not teach about the stack limit.