Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

I thought I understood recursion

functional.christmas

Post reply on HN
Print view View original

91–100 of 124 posts

Re: I thought I understood recursion

#91

Post by cannabis_sam »

ColinWright wrote: post #77
axilmar wrote: post #13

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't get it.

I 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…

Thanks 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.

Re: I thought I understood recursion

#92

Post by merijnv »

cjfd wrote: post #23
merijnv wrote: post #19

Earlier quoted context omitted.

I'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…

clearly 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.

> The thing is, every prime p gets passed through a filter that filters multiples of primes p' for all 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.

Re: I thought I understood recursion

#93

Post by grugagag »

GuB-42 wrote: post #62
baq wrote: post #7

> 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 progra…

In the end, it is all machine code. All that recursion, lazy evaluation, monads, lambdas, virtual methods and coroutines. In the end, they are all stack manipulation and jump instructions. High level languages are just a more convenient way of writing assembly. I like to take that approach when comparing languages. What a program might do in term of machine instructions, and see how I can make another language output…

Lets extend this analogy to books: all books are just letters and words writen on a page. And some pictures too. It doesn’t matter how a book is written as long as it produces letters, words and paragraphs and pictures. It doesn’t sound right, does it?

Re: I thought I understood recursion

#95

Post by collyw »

roenxi wrote: post #15
gear54rus wrote: post #9

Earlier quoted context omitted.

So 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 somethi…

Maybe 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 levera…

> Programming languages don't make people miserable.

JavaScript makes me miserable when I have to fix it.

Re: I thought I understood recursion

#96

Post by edflsafoiewq »

butterisgood wrote: post #94

It’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-pr...

This is not the Sieve (despite its name). For just one reason, the Sieve does not ever require testing divisibility.

Re: I thought I understood recursion

#97

Post by barbarbar »

collyw wrote: post #64
hans1729 wrote: post #24

Earlier quoted context omitted.

Don't know if you're serious, but for the most devs, the job is chosen for, not by, you

I have worked with a couple of devs who decide to pick and choose what they work on. Usually they are seen as important by management / company owners and not team players.

I have worked with them too.

Re: I thought I understood recursion

#98

Post by nradov »

grugagag wrote: post #93
GuB-42 wrote: post #62

Earlier quoted context omitted.

In the end, it is all machine code. All that recursion, lazy evaluation, monads, lambdas, virtual methods and coroutines. In the end, they are all stack manipulation and jump instructions. High level languages are just a more convenient way of writing assembly. I like to take that approach when comparing languages. What a program might do in term of machine instructions, and see how I can make another language output…

Lets extend this analogy to books: all books are just letters and words writen on a page. And some pictures too. It doesn’t matter how a book is written as long as it produces letters, words and paragraphs and pictures. It doesn’t sound right, does it?

That's not a fair extension of the analogy. An equivalent analogy would be that you can use any text editor or word processor to write a book.

Re: I thought I understood recursion

#99

Post by d--b »

m0skit0 wrote: post #90
d--b wrote: post #44

C# equivalent: IEnumerable filter(int p, IEnumerable xs) { foreach(var j in xs) if (j % p > 0) yield return j; } IEnumerable sieve(IEnumerable 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();

Less readable in my opinion and I'm more used to C# code than Haskell.

It's awful indeed. But it's a translation of what haskell does. The imperative version would be much more readable in any case...

Re: I thought I understood recursion

#100

Post by nradov »

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'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.
Post reply on HN