5 ms·
Recursion via Pascal
Recursion via Pascal by J. S. Rohl is one of a small number of books devoted entirely to recursion in programming.
- iwwr 16y agoPorting stuff from Pascal is prone to off-by-one errors due to 1-based arrays.
- redstripe 16y agoArrays can have any base in pascal including zero. Do you mean strings?
- TimJYoung 16y agoAs already mentioned, that's not correct. You can declare arrays with any indexing/bounds that you want: MyArray: array[1..10] of Byte; or if you want something that can be used as a buffer: MyCharArray: array[0..19] of Char; StrCopy(@MyCharArray,'Hello World'); // array acting like a 0-indexed Char buffer
- RiderOfGiraffes 16y agoLove the complexity gotcha in the power example: function p(x:real; n:integer):real; begin if n = 0 then p := 1 else if odd(n) then p := p( x, n div 2 ) * p( x, n div 2 ) * x else p := p( x, n div 2 ) * p( x, n div 2 ) end Can you see why this is O(n) and not O(lg n)? I've seen that (or its equivalent) in so many people's code. This is the one place where "pure" functional languages have such potential. If the function is guaranteed side-effect free then the calls can be memo-ised, and this routine becomes O(lg n) "for free".
- 3pt14159 16y agoIs it that p is double called the majority of the calculations, thereby making the function call itself twice when a simple "save" of the result would have stopped a geometrically growing tree? I've never studied this, just curious.
- RiderOfGiraffes 16y agoYes. Consider calling p with n=1. Then it takes one call. Now call it with n=2. It gets called twice with n=1, and you need to do the multiply. Thus T(2)=2 calls + 1 multiply. Now call it with n=4. Time taken is 2T(2) plus a multiply. Hence T(4)=2(2c+m)+m=4c+3m. Inductively we can prove that T(n)=n * c + m, where c is the time of a call, and m is the time of a multiply, and I'm ignoring small details. If you save the result of a call and reuse it then you get a different result, of course, and if you really want to learn how this works then you should try to figure it out.
- gabaix 16y agoSo what would be the operation to keep O(log n)? save p(x, n div 2) in memory?
- deleted 16y ago[deleted]
- TimJYoung 16y agoOne option would be to have the language (in this case Pascal) support a hint keyword that indicates that p is side-effect-free and doesn't modify any global data, or any data outside of its local scope. Then the compiler can use a simple common subexpression elimination optimization. The SQL 2003 standard does this with functions in order to aid the implementor's compiler/optimizer ability to optimize functions that don't modify or read any data and are purely functional.