Review: Introduction to Recursive Programming

It’s a good book over­all, but not out­stand­ing. The con­tent is not treated evenly be­tween chap­ters. Nonethe­less, there are some good chap­ters here and there:

• Chapter 1 and 2: The au­thor does a good job in­tro­duc­ing the con­cept of re­cur­sion in­tu­itively with plenty of ex­am­ples. Us­ing di­a­grams to de­com­pose and com­bine prob­lems is a good tech­nique for one new to re­cur­sion.
• Chapters 5 to 9: There is a wide range of ex­am­ples and ex­er­cises on dif­fer­ent types of re­cur­sion. Some of them are from in­ter­view ques­tions, which is a plus.

It could be a great book if the au­thor demon­strated more ex­am­ples with bet­ter ex­pla­na­tions on how to think re­cur­sively. Specif­i­cally, I want more ex­am­ples sim­i­lar to what is done for the Fibonacci se­quence.

Sometimes, es­pe­cially in the later chap­ters, the au­thor is too ver­bose in ex­plain­ing the code line by line, which makes the read­ing ex­pe­ri­ence less en­joy­able.

Python is used through­out the book, which is too easy for me. So, I opted to ex­plore Raku in­stead while fol­low­ing the ex­am­ples in the book. Due to the badly ex­pe­ri­ence when writ­ing Raku code in Neovim, I de­cided to use D lan­guage in­stead. Go­ing back to the code ex­am­ples, some are bad, par­tic­u­larly when the au­thor uses lists to rep­re­sent tree struc­tures. Draw­ing frac­tals us­ing re­cur­sion is a nice touch, though. I wish the book had more. The code for the re­cur­sive de­scent parser is too ver­bose for my taste.

Overall: 3.5/5. I def­i­nitely rec­om­mend some chap­ters of the book to new­bies, but not the whole book.

Code Examples & Exercises

The re­cur­sive ver­sion of ma­trix mul­ti­pli­ca­tion (Chapter 6.10) is re­ally not ef­fi­cient since there are 2 ma­trix al­lo­ca­tions oc­curred at each level of re­cur­sion. By sim­ply re­mov­ing the add_matrices_limits and us­ing += in­stead of = in the base case, we do not have to al­lo­cate for the two tem­po­rary ma­tri­ces.

A quick bench­mark shows a sig­nif­i­cant speedup:

Benchmarking recur_matmul:76 ms, 107 μs, and 5 hnsecs
Benchmarking recur_matmul2:1 ms, 490 μs, and 7 hnsecs

mergesort suf­fers the sim­i­lar is­sue, i.e., al­lo­cat­ing new ar­rays at each level of re­cur­sion. A bet­ter ap­proach is to use an aux­il­iary ar­ray and swap the roles of the in­put and aux­il­iary ar­rays at each level of re­cur­sion as men­tioned by (Sedgewick 1998).

void merge(int[] a, int[] aux, ulong low, ulong mid, ulong high) {
  ulong i = low, j = mid + 1;
  for (ulong k = low; k <= high; k++) {
    if (i > mid)              a[k] = aux[j++];
    else if (j > high)        a[k] = aux[i++];
    else if (aux[j] < aux[i]) a[k] = aux[j++];
    else                      a[k] = aux[i++];
  }
}
void _mergesort(int[] a, int[] aux, ulong low, ulong high) {
  if (high <= low) return;
  auto mid = low + (high - low) / 2;
  _mergesort(aux, a, low, mid);
  _mergesort(aux, a, mid+1, high);
  merge(a, aux, low, mid, high);
}
void mergesort(int[] a) {
  int[] aux = a.dup;
  _mergesort(a, aux, 0, a.length - 1);
}

I was ex­cited when see­ing the wood cut­ter prob­lem be­ing men­tioned in the book. How­ever, it is a shame that the code ex­am­ple does not demon­strate the sub­tlety of bi­nary search im­ple­men­ta­tion, i.e., how we cal­cu­late the mid­dle point for the max­i­mum find­ing prob­lem.

import std.algorithm;

bool cut(int c, int k, const int[] heights) {
  int total = 0;
  foreach (h; heights) total += max(h-c, 0);
  return total >= k;
}

int woodcutter(int k, int[] heights) {
  int low = 0, high = maxElement(heights);
  while (low < high) {
    int mid = (low + high + 1) / 2;
    if (!cut(mid, k, heights)) {
      high = mid - 1;
    } else {
      low = mid;
    }
  }
  return low;
}

int woodcutter2(int k, int[] heights) {
  int low = 0, high = maxElement(heights);
  int answer = 0;

  while (low <= high) {
    int mid = low + (high - low) / 2;
    if (cut(mid, k, heights)) {
      answer = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return answer;
}

Fractals

Here is what Opus 4.5 sug­gested for draw­ing Kocke curve:

import raylib;
void drawKnockLine(Vector2 start, Vector2 end, int n) {
  if (n == 0) {
    DrawLineEx(start, end, THINK, COLOR);
    return;
  }
  auto delta = Vector2Subtract(end, start);
  auto p1 = Vector2Add(start, Vector2Scale(delta, 1.0/3));
  auto p2 = Vector2Add(start, Vector2Scale(delta, 2.0/3));
  auto mid = Vector2Add(p1, Vector2Scale(delta, 0.5/3));
  auto peak = Vector2Add(mid, Vector2Rotate(Vector2Scale(delta, 1.0/6), -PI/3));
  drawKnockLine(start, p1, n - 1);
  drawKnockLine(p1, peak, n - 1);
  drawKnockLine(peak, p2, n - 1);
  drawKnockLine(p2, end, n - 1);
}

The mis­take is sub­tle though, in­stead of us­ing the delta vec­tor to cal­cu­late the peak point, we should use the vec­tor from p1 to p2.