8 ms·

I see someone disagreed with me. Not sure about what, but just in case I will show how to derive a formula for Fibonacci using the above. You be the judge if it

I see someone disagreed with me. Not sure about what, but just in case I will show how to derive a formula for Fibonacci using the above. You be the judge if it belongs in a LISP programming textbook, even though this particular result is very elementary. Recurrence relation for Fibonacci is F_k = F_(k-1) + F_(k-2) for k=> 2 with F_0 = F_1 = 1. Also, t^2 - t - 1 = 0 implies t = (1 + sqrt(5))/2, (1 - sqrt(5))/2. Both of these facts satisfy the conditions of the linked theorem and so we have F_n = x((1 + sqrt(5))/2)^n + y((1 - sqrt(5))/2)^n for n=>0. Now F_0 = x + y = 1 and F_1 = x(1 + sqrt(5))/2 + y(1 - sqrt(5))/2 = 1 from which it follows that x = (1 + sqrt(5))/2sqrt(5) and y = -(1 - sqrt(5))/2sqrt(5) meaning F_n = (1 + sqrt(5))/2sqrt(5)((1 + sqrt(5))/2)^n + (-1 + sqrt(5))/2sqrt(5)((1 - sqrt(5))/2)^n. This math (complete with a universe of theorems and their proofs) can obviously be extended in many different directions in such a way that it can take over your whole book.

wwweston 4y ago
I don't think anyone finds recurrence relations, closed form expressions, or their derivation controversial or disagreeable in any way. On the other hand, the implication that Lisp textbooks -- or other language texts that use fibonacci or like examples for recursion examples -- shouldn't be using simple recursive definitions as an illustration if there exists a closed form may well raise some eyebrows. What do you want, Collatz Sequences? Additionally, there's an air of attacking the sophistication of devs who choose Lisp specifically, which is the kind of thing that people frequently do find disagreeable (even if there's a reasonable case for it). Fibonacci and other linear recurrence relations are used because they're simple and often familiar intros that can help conceptualize the way recursion can reduce problems to smaller versions of themselves (which is very much mathematical thinking). They're not there because they represent limits of how Lisp devs generally do or should think.
- userxyz 4y ago
  > On the other hand, the implication that Lisp textbooks -- or other language texts that use fibonacci or like examples for recursion examples -- shouldn't be using simple recursive definitions as an illustration if there exists a closed form may well raise some eyebrows. I didn't imply that. I think the author laments the lack of math in LISP programming books beyond a couple of cliched examples he gave, well the "simple recursive definitions". He is not saying you shouldn't be using them, he is saying that is not adequate. That's too little. He is saying LISPers should go beyond that. My point was that you can definitely go above and beyond that into the math territory complete with coherent body of theory(a bundle of theorems and their proofs), but that will take you way off course. Especially, given that regular math textbooks contain all the relevant info. I am not even arguing the rest of what you said.
kazinator 4y ago
I agree with you that all that stuff is off topic in a textbook about Lisp. Some off-topic material is necessary in order to connect the programming topic with the real world. Too much of it will just distract from the focus and add bulk to the page count. That Fibonacci has a closed form it's completely irrelevant to teaching recursion as a programming technique. It could be mentioned in a small footnote giving some external reference. More relevant is the fact that the naive Fibonacci is terribly inefficient and can be vastly sped up by memoization. Even that is a problem that's not specific to the language and how to use recursion in that language. It has to do with using recursion well in any language, that belongs in an advanced chapter in a book which is not mainly about Lisp but about learning programming using Lisp. Lisp already has a reputation for being scary, which is unfounded, but there it is. A Lisp book which goes into numerous mathematical rabbit holes will probably just contribute to that meme and have a discouraging effect.

wwweston 4y ago

I don't think anyone finds recurrence relations, closed form expressions, or their derivation controversial or disagreeable in any way. On the other hand, the implication that Lisp textbooks -- or other language texts that use fibonacci or like examples for recursion examples -- shouldn't be using simple recursive definitions as an illustration if there exists a closed form may well raise some eyebrows. What do you want, Collatz Sequences? Additionally, there's an air of attacking the sophistication of devs who choose Lisp specifically, which is the kind of thing that people frequently do find disagreeable (even if there's a reasonable case for it). Fibonacci and other linear recurrence relations are used because they're simple and often familiar intros that can help conceptualize the way recursion can reduce problems to smaller versions of themselves (which is very much mathematical thinking). They're not there because they represent limits of how Lisp devs generally do or should think.

userxyz 4y ago
> On the other hand, the implication that Lisp textbooks -- or other language texts that use fibonacci or like examples for recursion examples -- shouldn't be using simple recursive definitions as an illustration if there exists a closed form may well raise some eyebrows. I didn't imply that. I think the author laments the lack of math in LISP programming books beyond a couple of cliched examples he gave, well the "simple recursive definitions". He is not saying you shouldn't be using them, he is saying that is not adequate. That's too little. He is saying LISPers should go beyond that. My point was that you can definitely go above and beyond that into the math territory complete with coherent body of theory(a bundle of theorems and their proofs), but that will take you way off course. Especially, given that regular math textbooks contain all the relevant info. I am not even arguing the rest of what you said.

kazinator 4y ago

I agree with you that all that stuff is off topic in a textbook about Lisp. Some off-topic material is necessary in order to connect the programming topic with the real world. Too much of it will just distract from the focus and add bulk to the page count. That Fibonacci has a closed form it's completely irrelevant to teaching recursion as a programming technique. It could be mentioned in a small footnote giving some external reference. More relevant is the fact that the naive Fibonacci is terribly inefficient and can be vastly sped up by memoization. Even that is a problem that's not specific to the language and how to use recursion in that language. It has to do with using recursion well in any language, that belongs in an advanced chapter in a book which is not mainly about Lisp but about learning programming using Lisp. Lisp already has a reputation for being scary, which is unfounded, but there it is. A Lisp book which goes into numerous mathematical rabbit holes will probably just contribute to that meme and have a discouraging effect.