How to read a recursive algorithm

Question

It is a newbie question and I hope it is the right section. I am counting the number of steps an algorithm requires to complete its calculation. Let's consider a factorization algorithm expressed in F# code:

let rec factorial n =
    if n = 0 then 1
    else n * factorial (n - 1)

If n = 0, it returns 1, otherwise it returns the multiplication between n and n - 1.

Now, suppose we feed the algorithm with n = 4. My question is: how the algorithm actually proceeds?

f1(4) = 4*3*2*1 = 24
f2(4) = 4*3 + 3*2 + 2*1 + 1*1 + 3*2 + 2*1 + 1*1 = 24

I think it is f2, because every loop of the algorithm calculates a single multiplication for a total of 7 multiplications and 6 additions, but I would like to be sure.

Answer 1

Your algorithm in no place sums things, so it surely is not f2!

Notice that inside your function factorial you call the function itself! Again! Let us write down the whole process, where each line we simplify a new bit

factorial 4 4 * (factorial(4 - 1)) 4 * (factorial(3)) 4 * (3 * (factorial(3 - 1))) 4 * (3 * (factorial(2))) 4 * (3 * (2 * (factorial(2 - 1)))) 4 * (3 * (2 * (factorial(1)))) 4 * (3 * (2 * (1 * (factorial(1 - 1))))) 4 * (3 * (2 * (1 * (factorial(0))))) 4 * (3 * (2 * (1 * 1))) 4 * (3 * (2 * 1)) 4 * (3 * 2) 4 * 6 24