Hacker News Reader

Comment by PaulHoule | Hacker News Reader

When you study the old AI programming you eventually realize that non-determinism rules and recursion drools. Recursion is great for certain things that would be hard otherwise (drawing fractals) but it shouldn’t be the first tool you reach for. It’s known to be dangerous in embedded systems because it can blow out the stack. Turns very simple O(N) problems into O(N^2) but unfortunately a generation of computer science pedagogues taught people that recursion > iteration because BASIC was the teaching language of the 1970s and first half of the 1980s and they couldn’t get over that Lisp, Forth, UCSD Pascal and other contenders didn’t make it to the finish.

View on HN

Ok, I'll bite.

  - Recursion allows you to show correctness both in programming and mathematics. 
  - plenty of compilers will reuse the current stack frame in a tail call.

Counterpoint: https://news.ycombinator.com/item?id=41974171

Tail call recursion doesn't turn the O(N^2) version of Fibonacci into O(N) but at least memoization turns it to O(N log N) or something. It's true that recursive algorithms can be easy to analyze. If you really knew your math you could do Fibonacci as O(1).

You cannot do Fibonacci in O(1). You can reasonably do it in O(log n), though. Recursive Fibonacci is not O(n^2) either, it’s exponential.

If you have O(1) arbitrary-precision floating-point operations in O(1), you can do Fibonacci in O(1) by Binet's formula. But you don't, so you can't.

Also, by a similar argument, the O(log n) by matrix exponentiation is really O(n log(n)^2 log(log(n))) by Schönhage-Strassen, I think. (The sequence is exponential in n, so the number of digits is O(n).) I may have miscounted the logs.

You’re exactly right, I omitted the Schonhage Strassen just to simplify the point.

https://en.m.wikipedia.org/wiki/Fibonacci_sequence#Closed-fo...

If exponentiation is done using floating-point arithmetic, this is O(1)

Floats only have a finite precision.

If you're fine getting wrong answers after the first 73, sure. Some people have higher standards than that.

Exponentiation is not a constant time operation, and floating points have finite precision.

Exponentiation is constant-time on floats. But as noted by sibling comments, the precision is a problem.

Everything is constant time is your precision is limited. Even the naive, recursive algorithm on integers is constant time if your integer size is limited (it will just be an exponentially big constant). To be able to meaningfully talk about complexity, you need to assume that something is not limited, and once you do that for floats, you’ll find that their exponentiation is no longer constant time.

no... you can do fibonacci as O(log n)... you cannot represent (1 + sqrt(5))/2 on a computer.

You literally just did! The problem is not representing the number, it's computing digits.

You totally can. Here is a O(log n) implementation of the Binet formula with infinite precision:

https://github.com/xyzzyz/FibBinet/blob/master/FibBinet.hs

There is a simple tail recursive implementation of fibonacci that is O(N) and doesn't use memoization. I'll leave it as an exercise for the reader.

The natural recursive implementation is exponential, and the memoized version is O(n)

> When you study the old AI programming you eventually realize that non-determinism rules and recursion drools.

This part I agree with.

Reply on news.ycombinator.com