Recursion via Pascal | Hacker News Reader

Recursion via Pascal

retroprogramming.com

8 pointsimpomatic8 comments

Recursion via Pascal by J. S. Rohl is one of a small number of books devoted entirely to recursion in programming.

Love 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".

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

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

So what would be the operation to keep O(log n)? save p(x, n div 2) in memory?

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

Porting stuff from Pascal is prone to off-by-one errors due to 1-based arrays.

As 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

Arrays can have any base in pascal including zero.

Do you mean strings?

Reply on news.ycombinator.com