Need explanation for the recursion process of a Lisp function checking if a number is a sum of non-repeated squares

Question

(defun sum-of-squares-p (n)
  (labels ((helper (i sum)
             (cond ((= sum n) t)
                   ((> sum n) nil)
                   ((> (* i i) n) nil)
                   (t (or (helper (+ i 1) (+ sum (* i i)))
                          (helper (+ i 1) sum))))))
    (if (= n 0)
        t
        (helper 1 0))))

I have this code from my college lesson. Its predicate, which returns t, if number n is sum of squares, which are not the same. E.G.: 10 = 3^2 + 1^2, 9 = 3^2, but 2 != 1^2 + 1^2, cause same same number(1) twice. I have trouble understanding how does this recursion works.

For example: (sum-of-squares-p 10)... steps:

1. (helper 1 0)

2. (helper 2 1)

3. (helper 3 5)

4. (helper 4 14) -> condition ((> sum n ) nil) = 14 > 10, returns nil and then

   the the second expression of or is called ->

   1. is it called like (helper 1 0) again, or is it called like (helper 5 5)?

Anyways, i have trouble understanding, how does this code sucessfuly T or NIL correctly, and i need your help to understand the process of getting to the result.

Im new to lisp, we only studied very few lessons, we learned only mathematical things in lisp, "if", "cond", "labels", "and", "or", and how to write iterative functions.

Could you please be able to explain me how this recursion deep down works please?

Is there any way to make the predicate easier, maybe with two or more functions?

I tried to write each step of recursion on the paper and didnt get my result.. I tried to write it also iteratively, but didnt work for me.

Answer 1

Common Lisp provides a trace macro. LispWorks has an extended version of it, which for example can trace subfunctions.

We need to define the function to trace:

CL-USER 38 > (defun sum-of-squares-p (n)
               (labels ((helper (i sum)
                          (cond ((= sum n) t)
                                ((> sum n) nil)
                                ((> (* i i) n) nil)
                                (t (or (helper (+ i 1) (+ sum (* i i)))
                                       (helper (+ i 1) sum))))))
                 (if (= n 0)
                     t
                   (helper 1 0))))
SUM-OF-SQUARES-P

Now we need to compile the interpreted function (because we defined it in a LispWorks Listener, which does not compile by default) in LispWorks:

CL-USER 39 > (compile 'sum-of-squares-p)
SUM-OF-SQUARES-P
NIL
NIL

Now we can trace the helper function, which is defined by a labels construct inside the sum-of-squares-p function.

CL-USER 40 > (trace (labels helper sum-of-squares-p))
((SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P))

Calling the function sum-of-squares-p will now generate the following trace output:

CL-USER 41 > (sum-of-squares-p 10)
0 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
  >> I   : 1
  >> SUM : 0
  1 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
    >> I   : 2
    >> SUM : 1
    2 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
      >> I   : 3
      >> SUM : 5
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
        >> I   : 4
        >> SUM : 14
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
        << VALUE-0 : NIL
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
        >> I   : 4
        >> SUM : 5
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
        << VALUE-0 : NIL
    2 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
      << VALUE-0 : NIL
    2 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
      >> I   : 3
      >> SUM : 1
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) > ...
        >> I   : 4
        >> SUM : 10
      3 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
        << VALUE-0 : T
    2 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
      << VALUE-0 : T
  1 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
    << VALUE-0 : T
0 (SUBFUNCTION (LABELS HELPER) SUM-OF-SQUARES-P) < ...
  << VALUE-0 : T
T

Answer 2

Other answers show the actual calls to the function. As far as the algorithm is concerned, here is why it works:

• You want to check if a number n is a sum of (all distinct) squares. There is an obvious base case, which is if n = 0 (and in that case the answer is true). This base case is illustrated by the last part of the function:

  (if (= n 0) t ...)

• Otherwise, there is nothing particularly clever going on: we will try to "guess" the possible squares that would hypothetically sum to n. Two observations:

  • we don't need to check for squares larger than n
  • each square appears 0 or 1 times in the "square decomposition" of n, so for each square smaller than n there are exactly two options (either we pick it, or we don't).

This is exactly what helper does: i represents the current "square" (actually, square root, i.e. we try to see if i*i goes into the decomposition, not i itself), and sum represents what we have built so far using the previous squares. The algorithm is as follows:

• if sum = n, then we are successful ! Indeed, as I said, sum represents what we have managed to build so far using squares, so if we get exactly n then we're done.
• on the other hand, if we have sum > n, then there is no point continuing: squares can't be negative, so we will never reach n again from there.
• the same thing happens if i*i is itself larger than the result: we don't need to continue, as squares from now on will only get larger.
• otherwise, and as explained above, we have two choice:
• either we decide to "take" this square in the decomposition, and so we call the helper function with arguments 1+i and sum + i*i
• or we do not take it: we move on to the next square but without changing the current value, and so we call (helper (1+ i) sum).

Indeed we can't guess beforehand whether or not i*i appears in the "square decomposition", so for each possible square, we try both.

Now, some (imo) good exercises could be:

1.Modify the previous function to return the actual decomposition, if it exists (for example as a list):

(defun square-decomposition (n)
    ;; some code here
  )

(square-decomposition 10) ; => (1 3)
(square-decomposition 35) ; => (1 3 5)

2.Write an iterative solution to the initial problem. A hint: use an array or a hash-table to store the "intermediate" computations. There are several solutions, but as far as I can tell, they more or less all use an additional data structure to "manually simulate" the call stack of the recursive version.

Answer 3

The values of variables don't change when you recurse - they are not shared between function calls.
(Recursive functions work exactly like non-recursive functions, and not like loops.)

That is, if i is 4 and sum is 5 in (helper (+ i 1) (+ sum (* i i)), they are also 4 and 5 in (helper (+ i 1) sum).

I find that the substitution method is often helpful, as it makes you focus on one "level" of recursion at a time.

Take the body of (helper 1 0) and substitute the values for the parameters:

(cond ((= 0 10) t)
      ((> 0 10) nil)
      ((> (* 1 1) 10) nil)
      (t (or (helper (+ 1 1) (+ 0 (* 1 1)))
             (helper (+ 1 1) 0))))

The three first conditions are clearly false, so we need to determine the value of the first branch of the or.
Substitute again:

(helper (+ 1 1) (+ 0 (* 1 1))):
-->
(cond ((= 1 10) t)
      ((> 1 10) nil)
      ((> (* 2 2) 10) nil)
      (t (or (helper (+ 2 1) (+ 1 (* 2 2)))
             (helper (+ 2 1) 1))))

The three first conditions are clearly false here as well, so we need to determine the first branch of the or for this case, too.
Substitute again:

(helper (+ 2 1) (+ 1 (* 2 2))):
-->
(cond ((= 5 10) t)
      ((> 5 10) nil)
      ((> (* 3 3) 10) nil)
      (t (or (helper (+ 3 1) (+ 5 (* 3 3)))
             (helper (+ 3 1) 5))))

And we need the first branch of that or, too:

(helper (+ 3 1) (+ 5 (* 3 3)))
-->
(cond ((= 14 10) t)
      ((> 14 10) nil) <--
      ((> (* 4 4) 10) nil)
      (t (or (helper (+ 4 1) (+ 14 (* 4 4)))
             (helper (+ 4 1) 14))))

Now the second condition is true, so we return nil.
Substitute it back in (helper 3 5), where we called this (leaving out the unneeded conditions):

(or nil
   (helper (+ 3 1) 5))

Now we need the second branch of the or.

(helper (+ 3 1) 5):
-->
(cond ((= 5 10) t)
      ((> 5 10) nil)
      ((> (* 4 4) 10) nil) <--
      (t (or (helper (+ 4 1) (+ 5 (* 4 4)))
             (helper (+ 4 1) 5))))

Now the third condition is false, so we return nil to (helper 3 5).

(or nil
    nil)

This is clearly nil, so we can go back another step to (helper 2 1):

(or nil
    (helper (+ 2 1) 1))

And so on.
It gets rather tedious to unfold recursion after a while, and it's best to learn to accept that the code is correct if all its constituent parts are correct.

That said, I would personally ditch the conditionals and stick to logical operations.
Something like this.

(defun sum-of-squares-p (n)
    (labels ((helper (i sum)
                     (or (= sum n) ; We succeed if we have found the sum, or
                         (and (< sum n) ; it is possible to find a sum
                              (or (helper (+ i 1) (+ sum (* i i))) ; in one of these
                                  (helper (+ i 1) sum)))))))
    (or (= n 0) (helper 1 0)))

Answer 4

So first of all, your explanation

I have this code from my college lesson. Its predicate, which returns t, if number n is sum of squares, which are not the same. E.G.: 10 = 3^2 + 1^2, 9 = 3^2, but 2 != 1^2 + 1^2, cause same same number(1) twice.

means: The function tests, whether one can express a number n using 1 or more different numbers (0 included) whose squares' sum gives n. Since 0 is included, all square numbers are automatically t when testing with this function. And as you say - the squares which build the sum are not allowed to repeat. So this function assesses whether a number n can be dissected into distinct squares which add up to n.

The strategy is:

• start with 0.
• The currently investigated number is called index and called therefore i.
• If n is 0, then in the case of i=0 squared is equal to n, thus t.
• We increase i by 1.
  • Either this number squared is n => t.
  • In case the index squared is already greater than n, then we break up because further increase will lead to higher numbers than n. And the result is nil.
• Then follows the more interesting investigation:
  • In case i^2 is smaller than n,
    • either if (i+1)^2 is n => t or
    • if i^2 plus any sum of squared numbers is n then the result will be t.
• If any of these is greater than n, we break up this chain and return nil.
• So in all the cases whether none of these apply, it depends on
  • whether the investigation of the next index number (1+ i)
    • with either the current sum or
    • with the next sum (+ (* i i) sum) is true.
• So either the next number (1+ i) itself is a square number,
• or the next numbers' square together
  • either with the current sum or
  • the current sum plus the current index's square gives n.

So this is:

(defun sum-of-squares-p (n)
  (labels ((helper (i sum)
             (cond ((or (= (* i i) n)
                        (= (+ (* i i) sum) n)) t)
                   ((or (> (* i i) n)
                        (> (+ (* i i) sum) n)) nil)
                   (t (or (helper (1+ i) (+ (* i i) sum))
                          (helper (1+ i) sum))))))
    (helper 0 0)))

And this is slightly more regularly formed than your example code.

Your example code is logically the same.

But instead of going on until (> sum n) applies, it is better to test, whether already (+ (* i i) sum) is greater than n. So this more regularly formed function is probably even slightly more performant since it makes fewer rounds of recursion.