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­gram 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. 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­cured at each level of re­cur­sion. By sim­ply re­mov­ing the add_matrices_limits and use += 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);
}