How Recursion works (tracing)

General form of recursion:

A function is recursive when it calls itself.

• There must be a base condition that will terminate the recursion, otherwise it will get into infinite calling.

Type fun(param) {
  if (<base condition>) {
    ...
    fun(param);
    ...
  }
} 

Simple example of a recursion:

void funi(int n) {
  if (n > 0) {
    printf("%d", n);
    funi(n - 1);
  }
}

void main() {
  int x = 3;
  funi(x);
}

• Recursive functions are traced in the form of a tree:

Printing is done at calling time.

    funi(3)
      /\
     /  \
    /    \
   3   funi(2)
        /\
       /  \
      /    \
     2     funi(1)
             /\
            /  \
           /    \
          1    funi(0)

Output : 3 2 1

Printing is done at returning time.

void fun2(int n) {
  if (n > 0) {
    fun2(n - 1);
    printf("%d", n);
  }
}

void main() {
  int x = 3;
  fun2(x);
}

          fun2(3)
            /
           /
          /
       fun2(2)
         /
        /
       / 
    fun2(1)
      /\
     /  \
    /    \
fun2(0)   1

Output : 1

Recursion always has two phases: calling phase and returning phase.

Generalizing Recursion

void fun (int n) {
if (n > 0) {
    // 1. Calling / Ascending
    fun (n - 1); // (anything operation to the function itself would also be returning)
    // 2. Returning / Descending
  }
}

Key difference between a loop and a recursion: a loop will only have an ascending phase, while recursions has both ascending and descending phases.