Visualising recursion in C

Question

I am trying to understand how recursion works in the factorial function. What should I print, so that I can see what actually happens during each recursion call? Here's the code:

#include <stdio.h>
#include <stdlib.h>


long factorial(long number) {
  if(number <= 1) {
    return 1;
  } else {
    return number * factorial(number - 1);
  }
}

int main() {
  int i;

  for(i = 0; i <= 10; i++) {
    printf("%2d ! = %ld\n", i, factorial(i));
  }

  return 0;
}

Answer 1

The following code

#include <stdio.h>
#include <stdlib.h>


long factorial (int level, long number){
    int result;
    printf("[%03d] Calculating: %d\n", level, number);

    if(number <= 1)
    {
        result = 1;
    }
    else
    {
        result = number * factorial(level+1, number - 1);
    }

    printf("[%03d] Returning:   %d\n", level, result);
    return result;
}
int main(){
    int i;
    for(i = 0; i <= 10; i++)
    {
        printf("%2d ! = %ld\n", i, factorial(0, i));
    }
    return 0;
}

gives this output

[000] Calculating: 10
[001] Calculating: 9
[002] Calculating: 8
[003] Calculating: 7
[004] Calculating: 6
[005] Calculating: 5
[006] Calculating: 4
[007] Calculating: 3
[008] Calculating: 2
[009] Calculating: 1
[009] Returning:   1
[008] Returning:   2
[007] Returning:   6
[006] Returning:   24
[005] Returning:   120
[004] Returning:   720
[003] Returning:   5040
[002] Returning:   40320
[001] Returning:   362880
[000] Returning:   3628800
10 ! = 3628800

Where [XXX] is the current level of recursion.

Answer 2

Try this

long factorial (long number){
if(number <= 1){
    return 1;
}else{
    return number * factorial(number - 1);

}
}

Assume we pass 4 as first parameter, then function evaluates to:

long factorial (long number /*==4*/){
if(4 <= 1){//false
    return 1;
}else{
    return 4 * factorial(4 - 1);

}
}

Note return in else can't finish, because it calls another function - factorial (4-1). So 4 must be multiplied by the result of factorial (3). So it goes and executes factorial(3).

Now we get

long factorial (long number /*==3*/){
if(3 <= 1){//false
    return 1;
}else{
    return 3 * factorial(3 - 1);

}

}

But again the return here can't finish, since it calls factorial for 3-1=2.

Now one needs to evaluate factorial (2), result of which will be multiplied by 3 and passed to previous return. Again:

long factorial (long number /*==2*/){
if(2 <= 1){//false
    return 1;
}else{
    return 2 * factorial(2 - 1);

}

}

We have similar problem. But now when executing factorial (2-1) the function will immediately return 1, hence above line will return 2.

This result will be plugged to the result of previous return, giving 2*3; this result - 6 - will be plugged in previous return and yield 6*4, which is the final result 24.