COMP1927 - Recursion

Recursion is nice because it is concise and natural (e.g. factorial is naturally recursive).

Traps in recursion

  • Forgetting to put in a base case
  • Putting the base case in the wrong place
  • Failing with the inductive case (e.g. n calls n)

Recursion v Iteration Efficiency

  • Recursion is an elephant; every function call requires a stack frame.
  • Iteration is bacteria; there is virtually no memory use, and is very fast.

Forever Recursion

Recursion without a base case eventually bottoms out with a memory crash.

If we want to recursively call main, (e.g.)

// recmain.c
  #include <stdio.h>
  int main() {
     int i = 0;
     printf("%d\n", ++i);
     return main();

it will just print 1, 1, 1, 1, etc

To stop this happening we could do one of three things:

  • make i a global variable
  • make i a static variable
  • change argc and pass that in (test that)