9 ms·
I thought I understood recursion
- millstone 7y agoOoh, what's the time and space complexity of `primes`?
- Rerarom 7y agoPrimes is in p
- OscarCunningham 7y agoReturning the nth prime is not known to be in P.
- Rerarom 7y agoI know, I was being silly.
- cjfd 7y agoClearly much worse than the original solution. Basically, a nested sequence of filters is built, one to filter out multiples of each prime number. One way in which the complexity of this is bad is that if you want prime numbers < N you only need to filter out primes smaller than sqrt(N). It is telling that the first solution contains an sqrt but not the second one.... These kind of functional solutions are very cute mathematically, but... I once wrote this way of generating an infinite list of primes in unlambda. That was kind of interesting to do.
- merijnv 7y ago> One way in which the complexity of this is bad is that if you want prime numbers < N you only need to filter out primes smaller than sqrt(N). It is telling that the first solution contains an sqrt but not the second one.... That's not really true, though, because that filter is applied lazily, so it only get evaluated up until the Nth prime and no further.
- merijnv 7y agoI'd say O(n) for both. The generated list only contains primes, so that's straightforward linear. Then there is the recursive sieving, which adds an additional pass over the sieve list for every prime we've found so far, we need keep the computation of each pass in memory, so that's some additional memory that's also linear. The time complexity is less obvious, each prime adds an additional pass to evaluate, so that seems linear, but each new pass only applies to a list that already had all the previous passes filtered out, so that's not technically linear, but I find it hard to determine how much it actually is.
- cjfd 7y agoclearly O(n^2) for time. Well, perhaps O(n^2/log n) or something, but that is not much different. The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p.
- merijnv 7y ago> The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all p' < p But the filter for multiples of 3 only sees the values that weren't already filtered by 2. So if we have N filters we don't evaluate all N filters for each value. The 2 is applied to everything, the 3 filter is only applied to things that are not multiples of 2, the 5 filter is only applied to things that aren't multiple of 2 and 3, etc. That doesn't sound very quadratic to me.
- cjfd 7y agoThe thing is that the prime numbers have to go through all of the filters. Although the prime numbers are a minority among the numbers they are not a very small minority. In fact, a random number N has about a probability of 1/log(N) to be prime. So that could reduce N^2 to maybe N^2/log(N) but not any further. So I suppose the complexity actually is somewhere between N^2 and N^2/log(N), but that is not much less than N^2. The trick of only checking primes smaller than sqrt(N) reduces the complexity to N^1.5, also maybe involving some division by log(N), but that is actually an improvement in the exponent.
- deleted 7y ago[deleted]
- twobat 7y agoWhat's up with the influx of christmas domains here on HN?
- afandian 7y agoPerhaps it correlates to the influx of Christmas?
- halvdan 7y agoI wondered the same, eventually found https://bekk.christmas/ https://bekk.christmas/ with some more information.
- cstuder 7y agoIt's a collection of advent calendars from a norwegian agency with fun TLDs: https://blogg.bekk.no/introducing-bekk-christmas-ad01660ccadf https://blogg.bekk.no/introducing-bekk-christmas-ad01660ccad...
- joppy 7y ago‘Tis the season
- baq 7y ago> My background is in OO programming, mostly using C#. C# being the versatile language it is, I have had the perception that whatever you do in other programming languages, you can with a little more code and hassle achieve in C# as well. If need be, I can program C# using a functional paradigm. And, of course I use recursion all the time. I know all there is to know about recursion. IME there are two kinds of programmers: ones who learned a single language deeply and have almost religious confidence that it's the best thing ever, even if they try to approach other languages with an open mind (i don't blame them, i was like that a couple decades ago, too) and some who understand that tools are just that - tools, which you should pick accordingly to the problem you want to solve, because the other way ends up in a tail-wags-dog situation. the blog post sounds like the author has realized that and started a journey from the first type to the second type, which is to be commended. good job.
- gear54rus 7y agoSo if you consider some stack to be inferior (maybe because its highly inconsistent in its design or it only runs on closed and locked down platforms or whatever) you still should just dismiss it as 'oh its just a tool' instead of accepting that it's shitty and makes you miserable when working with it? Why wouldn't I want to work with best thing ever if it helps me keep my sanity every day? Do you want to use something that makes you miserable? Is any language including those designed by 3 year old 'just a tool' that is to be used despite obviously being shitty? Never understood that argument.
- wodenokoto 7y agoThe argument is to use the right tool for the right job and not just the hammer that you’ve become an expert in. If you know of a tool that is the wrong tool for every job, then yes, it’s still just a tool. Just use something else.
- roenxi 7y agoMaybe you should look within yourself and fix up whatever part of your personality is making you miserable? I'm not being flippant. Programming languages don't make people miserable. There isn't really an argument, just an observation that the most efficient way of thinking about programming is in data structures and algorithms which are mostly language independent. Nobody should be spending most of their time leveraging language features, so it isn't critical to use any particular language. I have a large range of pens of different quality. I have a favourite pen. But I'm willing to use any pen if I need to write something down. My focus is on composing a message, not on worrying about the quality of my calligraphy or the occasional scratchy mark. If 'm going to be writing all day I'd rather have my favourite pen but any one will do.
- cjfd 7y agoTo understand recursion you must first understand recursion.
- martin1975 7y agoThe first rule of recursion is we do not talk about recursion. The second rule of recursion is we do not talk about recursion. The third rule of recursion is without a base case, you have no recursion. The fourth rule of recursion is it breaks you in two or more pieces.
- BerislavLopac 7y agoThe fifth rule of recursion is that it is not really recursion if it isn't tail-call optimised.
- tr352 7y agoSo a recursive tree search is not really recursive?
- BerislavLopac 7y agoOh no, it is really recursive -- it's just not "real recursion" (TM). ;)
- js8 7y agoWhenever I need to think about recursion, I always refer back to the time when I understood it.
- axilmar 7y agoI do not get what this publication is trying to say. Is Haskell better than C#? are Haskell programs shorter than C#? is recursion difficult? is recursion difficult in C#? I don't get it.
- ColinWright 7y agoI can't tell if you're seriously enquiring, or simply being snarky. However, taking your comment at face value ... To me this post is saying that in some languages (in this case Haskell) there are ways of working that are hard to emulate in other languages (in this case C#). The post is talking through a specific example of this, and pointing out that if you only know one language (in this case C#) then you might be missing out on styles of thought that can help in solving certain problems. The post isn't about one language being better or worse in absolute terms, it's about broadening your range as a programmer so you are aware of other techniques and styles of thought. To go all "new age-y" it's about enlightenment. Usually Lisp is the language used to help programmers achieve enlightenment, but other options exist, such as fexl, Haskell, and others. Seriously, many languages are "about the same," but some really do make you think differently. You can be an excellent and productive programmer without them, and the vast majority of programmers never try to step outside the bubble of Imperative & OO languages, but you will be missing out if you don't at some stage embrace one of these other "pure(ish) functional" languages that is genuinely different. YMMV Some reading: * https://www.defmacro.org/ramblings/lisp.html https://www.defmacro.org/ramblings/lisp.html * https://stackoverflow.com/questions/2036244/whats-so-great-about-lisp https://stackoverflow.com/questions/2036244/whats-so-great-a... Search for "Lisp Enlightenment" and cull mercilessly.
- cannabis_sam 7y agoThanks for a great explanation of a weird topic, that I’ve struggled to do put into words! I’ve had a few similar experiences in my humble programming education. The first was at uni, having to learn c, c++ and python in one semester, after only using java for the first two semesters. (And a tiny bit of php and visual basic before that) The second was exposure to scheme/racket and real functional programming. The third time was the most amazing mix of haskell, type theory, lambda calculus, logics, agda, category theory, proof theory, model theory and just theoretical computer science in general. It leaves you with this wonderful and strange view of programming, without any of the concrete computational models.
- tromp 7y agoThe Haskell code can be slightly simplified to nth :: Integral a => Int -> Maybe a nth n | n < 1 = Nothing | True = Just (primes !! (n-1)) primes :: Integral a => [a] primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] Note that this is not a genuine sieve [1] [1] https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
- martin1975 7y ago"It is rather an attempt to get my head around functional programming, and to me Haskell doesn’t seem to have any practical application beyond that." Cardano/ADA's core Ouroboros protocol was entirely written, with formal proofs, in Haskell. It is by far the most serious attempt at proof of stake in the crypto industry. I think what you're really saying is, you won't find many jobs out there w/Haskell as a requirement... but I wouldn't go as far as saying Haskell has no purpose past teaching FP. It certainly is the poster child of FP, however it is not without practical/industrial use. You just have to look harder to see where it's being used.
- tempestn 7y agoOr maybe it was just a joke...
- javajosh 7y ago>You just have to look harder to see where it's being used. This is where advocacy slips over the line into a kind of blind faith evangelism -- with an added pinch of pedantry peculiar to our field. I will state without proof that every language ever invented is currently being used for something practical somewhere. E.g. someone has a useful shell utility they wrote in Brainfuck that they run every day and that they love. This does not mean that BF has 'practical application' in the usual sense of the phrase. In the same way, just because there is a real program written in Haskell somewhere does not mean it has practical application. IMHO a language (or a tool in general) should have a community of practitioners that regularly think in and create with the tool, and a good signal that that is happening are the number of open-source releases in that language. I have never in my life installed a Haskell program, or known of anyone installing one. (The exception being this one Haskell fan at JPL who loved talking about the language and the lambda calculas, but to my knowledge, never wrote anything real in it, and he just installed learning toys, not utilities.) All that said, there are some good examples of unpopular tools that enjoyed success later in life. Quaternions lost to vectors historically, but graphics programmers rediscovered their benefits and resurrected them. Maybe Haskell will have it's time, but that time is not now.
- leadingthenet 7y ago
- neilwilson 7y agoCan you cheat? #!/usr/bin/env ruby require 'prime' def find_prime(nth) Prime.lazy.drop(nth-1).first end
- leibnitz27 7y agoSure you can. Here's a super grotty (and expensive) c# version. static IEnumerable<int> infinite() { int x = 2; while (true) { yield return x++; } } static IEnumerable<int> primes(IEnumerable<int> l) { int head = l.First(); yield return head; foreach (var x in primes(l.Skip(1).Where(x => x % head != 0))) yield return x; } static void Main(string[] args) { System.Console.WriteLine(string.Join(",", primes(infinite()).Take(20).Select(x => x.ToString()))); }
- leibnitz27 7y ago(and yes, the nested yield is ABSOLUTELY an anti-pattern. They did promise to do a bulk yield at some point, I haven't used C# in a few years so don't know if I'm out of date!)
- cousin_it 7y agoUsing functional programming to find primes is tricky: https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf Melissa O'Neill shows that the typical FP sieve has worse big-O complexity than imperative. https://wiki.haskell.org/Prime_numbers#Sieve_of_Eratosthenes https://wiki.haskell.org/Prime_numbers#Sieve_of_Eratosthenes The Haskell wiki gives several sieve implementations and can't figure out the big-O complexity. (The imperative sieve is O(n log log n).)
- d--b 7y agoC# equivalent: IEnumerable<int> filter(int p, IEnumerable<int> xs) { foreach(var j in xs) if (j % p > 0) yield return j; } IEnumerable<int> sieve(IEnumerable<int> s) { var p = s.First(); yield return p; foreach(var e in sieve(filter(p,s.Skip(1)))) yield return e; } var n = sieve(Enumerable.Range(2, 10000)).Skip(10).First();
- m0skit0 7y agoLess readable in my opinion and I'm more used to C# code than Haskell.
- jayrwren 7y agocame here to point out that the author doesn't seem to know C# very well if they don't know about Enumerable.Range.
- lostmsu 7y agoWhy did you write own filter, when you could just do .Where(j => j % p > 0)?
- deleted 7y ago[deleted]
- meigwilym 7y ago> This led me to understand how little I had understood. The unknown unknowns become known.
- jpeg_hero 7y agoI was thinking about this recently: is there ever a reason to put recursion in an everyday “workman” code base? Seems like it would be so out of place in a real industry code base, like a infinite loop waiting to happen. There are always better more readable and maintainable ways to accomplish the same thing.
- pjc50 7y agoThere are contexts where it's banned (MISRA, and other embedded scenarios). But it's very hard to work with tree structures without recursion - if you're not careful you just end up with an explicit stack rather than using the software stack. In situations where you think auto-vectorisation might help, you definitely want to do it as iteration. This is partly why I like the system of transformers that LINQ is built out of; you can specify your query in a natural nice functional manner, and then let the optimizer convert it into a fast query.
- yen223 7y agoLoops are also infinite loops waiting to happen, yet we still use them :) The reason one might want to use recursion is when you're working on a data structure that is recursive in shape, like trees. And trees are very common, the Hacker News comments are one such example.
- Smaug123 7y agoSure there is: it lets you express loops immutably. Rather than `state := null; while condition do: mutate-state-and-recompute-condition`, you can do `let loop(state) = if shouldContinue(condition) then loop(newState) else resultOfTheLoop`. Rely on the tail-call optimiser to compile this to a genuine imperative loop. This looks very odd the first few times you see it, but it's much harder to get wrong.
- snak 7y agoHere's my code golf attempt in C#. public static List<int> Sieve(int n) { bool[] arr = Enumerable.Range(0, n).Select(i => true).ToArray(); Enumerable .Range(2, (int) Math.Sqrt(n) - 2) .ToList() .ForEach(i => { if (arr[i]) Enumerable.Range(0, (n - (i * i)) / i).ToList().ForEach(j => arr[j * i + (i * i)] = false); }); return arr.Select((b, i) => b ? i : 0).Where(i => i > 0).ToList(); }
- pjc50 7y agoIt looks much more functional if you get familiar with LINQ. var allPossibleNumbers = Enumerable.Range(3, max-3); var possiblePrime = allPossibleNumbers .AsParallel() .Where(n => Enumerable.Range(2, (int)Math.Sqrt(n)) .All(i => n % i != 0) ); (from https://codereview.stackexchange.com/questions/6115/sieve-of-eratosthenes-in-c-with-linq https://codereview.stackexchange.com/questions/6115/sieve-of... )
- deleted 7y ago[deleted]
- aurbano 7y agoThis was such a nice read! I've only ever written Java & JavaScript really, and Haskell is always at the top of the list of things I want to learn! When I got to the 7 line snippet at the end I was blown away by the elegance, and the fact that I couldn't really understand exactly what each thing did. So I decided to spend a few hours going through it character by character and documented my process here [1] in case it was useful to anyone else. I'll continue by reading a book on Haskell, but open to any advice from anyone on good ways to get into it! [1] https://aurbano.eu/note/2019-12-18-journey-into-haskell/ https://aurbano.eu/note/2019-12-18-journey-into-haskell/
- mettamage 7y agoFun blog post! I know nothing about Haskell as well. Quite casual, just what I needed. Thanks for writing it up! One blogging tip (note: the rest was perfect): if you would've chopped the following in 2 or 3 lines, then the casual style would be perfect. > primes n = take n $ sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `rem` p > 0] sieve [] = [] I feel that it'd be really hard to do though.
- aurbano 7y agoThanks! And good idea, I just updated it breaking that down a bit more :)
- deepaksurti 7y agoOne of the most beautiful introduction to recursion is in Chapter 8 using dragon stories, of the `Common Lisp: A Gentle Introduction to Symbolic Computation` book by David S. Touretzky. [1], is the link to the free pdf. [1] https://www.cs.cmu.edu/~dst/LispBook/book.pdf https://www.cs.cmu.edu/~dst/LispBook/book.pdf
- butterisgood 7y agoIt’s the Sieve of Eratosthenes. Probably someone has written it in C#. Here is a python version. https://www.google.com/amp/s/www.geeksforgeeks.org/python-program-for-sieve-of-eratosthenes/amp/ https://www.google.com/amp/s/www.geeksforgeeks.org/python-pr...
- edflsafoiewq 7y agoThis is not the Sieve (despite its name). For just one reason, the Sieve does not ever require testing divisibility.
- edflsafoiewq 7y agoThis is the equivalent Python: https://pastebin.com/CXfaNHPC https://pastebin.com/CXfaNHPC
- nradov 7y agoDepending on the particular language and platform, it can be quite dangerous to use recursion in production software due to the risk of a stack overflow. To be safe you have to first determine analytically that this can never happen. For algorithms that manipulate tree data structures it's often safer to avoid real recursion and instead sort of simulate recursion using a list or stack data structure allocated on the heap. At least that gives you a better opportunity to fail gracefully if the input data is too large to process within your resource constraints.
- setr 7y agoTbf most code doesn't encounter trees deep enough to generate a stack overflow. It's more of a concern with things like mutual recursion (multiplying your frame depth at each step, instead of just +1) or if your recursion depth is based on unbounded user input (eg iterating over an AST, or this code snippet)
- vincnetas 7y agoJava one liner : Stream.iterate(1, i -> i + 1).filter(i -> !IntStream.range(2, i).filter(v -> i % v == 0).findAny().isPresent()).skip(100000).findFirst();
- mbrodersen 7y agoGood developers can solve problems and be productive with any programming language/tools. Bad developers can't solve anything unless they use the one specific tool they know.
- mbrodersen 7y agoAnother way to put it is that if you always "use the best tool in the tool box" then you better have more than just one tool in the tool box.