The Mystery M Function (ITA Puzzle Archive, Analyzed)

Please refer to the mystery M function problem on this page.

Analysis

(defun m (i j k)
  (cond ((= i 0) (1+ k))
        ((and (= i 1) (= k 0)) j)
        ((and (= i 2) (= k 0)) 0)
        ((= k 0) 1)
        (t (m (1- i) j (m i j (1- k))))))

Let us look at the exit conditions for this recursive function ’m’. One of the exit conditions is when k equals zero. Now look at the recursive call. The recursive call fetches a value of k by replacing it with a call to ’m’ while decrementing k. As such k will reach 0, when it will return 1.

So it can be seen that the terminating condition of k equals zero returns 1 which is used as a value for k itself.

Evaluation

The evaluation will never terminate!