3 ms·
About Euclid’s Algorithm: I actually implemented several times at work, it is useful when you are dealing with periodic events, which is common in real time sys
by GuB-42 6y ago
About Euclid’s Algorithm: I actually implemented several times at work, it is useful when you are dealing with periodic events, which is common in real time systems. The typical question is: a task has to do something every 20, 30 and 40ms, at which period should you schedule your task (minor cycle)? The answer is gcd(20,30,40)=10ms and it can be computed using the Euclid's Algorithm.
But in most languages, Euclid's Algorithm is actually better implemented with a loop, and it brings me to one thing I realized about recursion that isn't commonly taught.
At a low level, recursion is implemented with a stack, so if you have a stack, you don't actually need to call functions to implement a recursive algorithm, in fact, many recursive algorithms don't need a stack at all (tail recursion). A recursive function call just means "remember my position and all local variables" and a return means "go back to where I was".
One advantage of this "machine first" thinking that it can help with optimization. By thinking about the stack, you may realize that you don't need to remember all local variables, that the call is always made from the same place so you don't need to remember your position. You may even realize that a stack, which is the natural data structure of recursion is not actually the best, for example, an array might be better, which, by the way, is one of the basis of dynamic programming.
And if you get to functional programming later, understanding what the machine does behind the scenes can give you a better grasp of the idea.
- kadoban 6y agoUsing an explicit stack can also be a good idea because several languages have a recursion limit, or some implicit restriction. Often those aren't very easy to modify either. So an explicit stack is far better since the alternative can be that you just crash fairly arbitrarily.
- polishdude20 6y agoCan you explain the scheduling part in a bit more detail?