TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

I thought I understood recursion

118 点作者 bendiksolheim超过 5 年前

21 条评论

baq超过 5 年前
&gt; 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.<p>IME there are two kinds of programmers: ones who learned a single language deeply and have almost religious confidence that it&#x27;s the best thing ever, even if they try to approach other languages with an open mind (i don&#x27;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.
评论 #21823858 未加载
评论 #21823807 未加载
评论 #21823610 未加载
评论 #21823412 未加载
评论 #21823410 未加载
cousin_it超过 5 年前
Using functional programming to find primes is tricky:<p><a href="https:&#x2F;&#x2F;www.cs.hmc.edu&#x2F;~oneill&#x2F;papers&#x2F;Sieve-JFP.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.hmc.edu&#x2F;~oneill&#x2F;papers&#x2F;Sieve-JFP.pdf</a><p>Melissa O&#x27;Neill shows that the typical FP sieve has worse big-O complexity than imperative.<p><a href="https:&#x2F;&#x2F;wiki.haskell.org&#x2F;Prime_numbers#Sieve_of_Eratosthenes" rel="nofollow">https:&#x2F;&#x2F;wiki.haskell.org&#x2F;Prime_numbers#Sieve_of_Eratosthenes</a><p>The Haskell wiki gives several sieve implementations and can&#x27;t figure out the big-O complexity. (The imperative sieve is O(n log log n).)
aurbano超过 5 年前
This was such a nice read! I&#x27;ve only ever written Java &amp; JavaScript really, and Haskell is always at the top of the list of things I want to learn!<p>When I got to the 7 line snippet at the end I was blown away by the elegance, and the fact that I couldn&#x27;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.<p>I&#x27;ll continue by reading a book on Haskell, but open to any advice from anyone on good ways to get into it!<p>[1] <a href="https:&#x2F;&#x2F;aurbano.eu&#x2F;note&#x2F;2019-12-18-journey-into-haskell&#x2F;" rel="nofollow">https:&#x2F;&#x2F;aurbano.eu&#x2F;note&#x2F;2019-12-18-journey-into-haskell&#x2F;</a>
评论 #21824517 未加载
d--b超过 5 年前
C# equivalent:<p><pre><code> IEnumerable&lt;int&gt; filter(int p, IEnumerable&lt;int&gt; xs) { foreach(var j in xs) if (j % p &gt; 0) yield return j; } IEnumerable&lt;int&gt; sieve(IEnumerable&lt;int&gt; 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();</code></pre>
评论 #21826128 未加载
评论 #21824744 未加载
评论 #21826677 未加载
tromp超过 5 年前
The Haskell code can be slightly simplified to<p><pre><code> nth :: Integral a =&gt; Int -&gt; Maybe a nth n | n &lt; 1 = Nothing | True = Just (primes !! (n-1)) primes :: Integral a =&gt; [a] primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x &lt;- xs, x `mod` p &#x2F;= 0] </code></pre> Note that this is not a genuine sieve [1]<p>[1] <a href="https:&#x2F;&#x2F;www.cs.hmc.edu&#x2F;~oneill&#x2F;papers&#x2F;Sieve-JFP.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.hmc.edu&#x2F;~oneill&#x2F;papers&#x2F;Sieve-JFP.pdf</a>
martin1975超过 5 年前
&quot;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.&quot;<p>Cardano&#x2F;ADA&#x27;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.<p>I think what you&#x27;re really saying is, you won&#x27;t find many jobs out there w&#x2F;Haskell as a requirement... but I wouldn&#x27;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&#x2F;industrial use. You just have to look harder to see where it&#x27;s being used.
评论 #21823664 未加载
评论 #21823834 未加载
评论 #21823644 未加载
pjc50超过 5 年前
It looks much more functional if you get familiar with LINQ.<p><pre><code> var allPossibleNumbers = Enumerable.Range(3, max-3); var possiblePrime = allPossibleNumbers .AsParallel() .Where(n =&gt; Enumerable.Range(2, (int)Math.Sqrt(n)) .All(i =&gt; n % i != 0) ); </code></pre> (from <a href="https:&#x2F;&#x2F;codereview.stackexchange.com&#x2F;questions&#x2F;6115&#x2F;sieve-of-eratosthenes-in-c-with-linq" rel="nofollow">https:&#x2F;&#x2F;codereview.stackexchange.com&#x2F;questions&#x2F;6115&#x2F;sieve-of...</a> )
deepaksurti超过 5 年前
One 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.<p>[1] <a href="https:&#x2F;&#x2F;www.cs.cmu.edu&#x2F;~dst&#x2F;LispBook&#x2F;book.pdf" rel="nofollow">https:&#x2F;&#x2F;www.cs.cmu.edu&#x2F;~dst&#x2F;LispBook&#x2F;book.pdf</a>
leibnitz27超过 5 年前
Sure you can. Here&#x27;s a super grotty (and expensive) c# version.<p><pre><code> static IEnumerable&lt;int&gt; infinite() { int x = 2; while (true) { yield return x++; } } static IEnumerable&lt;int&gt; primes(IEnumerable&lt;int&gt; l) { int head = l.First(); yield return head; foreach (var x in primes(l.Skip(1).Where(x =&gt; x % head != 0))) yield return x; } static void Main(string[] args) { System.Console.WriteLine(string.Join(&quot;,&quot;, primes(infinite()).Take(20).Select(x =&gt; x.ToString()))); }</code></pre>
评论 #21823635 未加载
nradov超过 5 年前
Depending 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&#x27;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.
评论 #21828039 未加载
snak超过 5 年前
Here&#x27;s my code golf attempt in C#.<p><pre><code> public static List&lt;int&gt; Sieve(int n) { bool[] arr = Enumerable.Range(0, n).Select(i =&gt; true).ToArray(); Enumerable .Range(2, (int) Math.Sqrt(n) - 2) .ToList() .ForEach(i =&gt; { if (arr[i]) Enumerable.Range(0, (n - (i * i)) &#x2F; i).ToList().ForEach(j =&gt; arr[j * i + (i * i)] = false); }); return arr.Select((b, i) =&gt; b ? i : 0).Where(i =&gt; i &gt; 0).ToList(); }</code></pre>
butterisgood超过 5 年前
It’s the Sieve of Eratosthenes. Probably someone has written it in C#.<p>Here is a python version.<p><a href="https:&#x2F;&#x2F;www.google.com&#x2F;amp&#x2F;s&#x2F;www.geeksforgeeks.org&#x2F;python-program-for-sieve-of-eratosthenes&#x2F;amp&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.google.com&#x2F;amp&#x2F;s&#x2F;www.geeksforgeeks.org&#x2F;python-pr...</a>
评论 #21825850 未加载
jpeg_hero超过 5 年前
I was thinking about this recently: is there ever a reason to put recursion in an everyday “workman” code base?<p>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.
评论 #21827271 未加载
评论 #21823914 未加载
评论 #21824014 未加载
cjfd超过 5 年前
To understand recursion you must first understand recursion.
评论 #21823527 未加载
评论 #21823502 未加载
mbrodersen超过 5 年前
Good developers can solve problems and be productive with any programming language&#x2F;tools. Bad developers can&#x27;t solve anything unless they use the one specific tool they know.
评论 #21841359 未加载
meigwilym超过 5 年前
&gt; This led me to understand how little I had understood.<p>The unknown unknowns become known.
vincnetas超过 5 年前
Java one liner :<p><pre><code> Stream.iterate(1, i -&gt; i + 1).filter(i -&gt; !IntStream.range(2, i).filter(v -&gt; i % v == 0).findAny().isPresent()).skip(100000).findFirst();</code></pre>
millstone超过 5 年前
Ooh, what&#x27;s the time and space complexity of `primes`?
评论 #21823466 未加载
评论 #21823473 未加载
评论 #21823868 未加载
评论 #21823434 未加载
axilmar超过 5 年前
I 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&#x27;t get it.
评论 #21824052 未加载
twobat超过 5 年前
What&#x27;s up with the influx of christmas domains here on HN?
评论 #21823267 未加载
评论 #21823226 未加载
评论 #21823262 未加载
评论 #21823273 未加载
neilwilson超过 5 年前
Can you cheat?<p>#!&#x2F;usr&#x2F;bin&#x2F;env ruby require &#x27;prime&#x27;<p>def find_prime(nth) Prime.lazy.drop(nth-1).first end