0

I'm trying to implement a recursive procedure in Scheme that takes the square of the number without using multiplication by using the formula n^2=1+3+5+...+(n+n-1). The if(< n 0) statement is in case a negative number is the argument. I know I could easily just use abs but I wanted to try coding it without abs.

When (Square1 2) is called it returns the correct value, but when I called (Square1 -2) it gets stuck in the recursive call.

I think I managed to narrow it down to the Square1(+ n -1) being the cause of the problem, but I am not sure why this is causing a problem. I tried programming this using the same logic in Java and it seems that my logic is correct. This is my first functional language so there is probably something I am not understanding. 

(define Square1
  (lambda (n)
    (if (= n 0) 
        0)
    (if (< n 0)
        (Square1 (* -1 n)))
    (if (= n 1)
        1
        (+ (+ (+ n n) -1) (Square1 (+ n -1))))))
Óscar López
  • 232,561
  • 37
  • 312
  • 386
Edward Wong
  • 39
  • 1
  • 6
  • 1
    You need to read more about Scheme's syntax. For starters, the first IFs in your code are useless, only the last one returns a result. Why? because for them to be useful, all IFs must have an ELSE part; some Scheme dialects even _force_ you to write them in this way, to avoid confusions such as the ones you're facing right now. – Óscar López Apr 13 '19 at 21:11
  • @ÓscarLópez The formula works for 5 as well. – Edward Wong Apr 13 '19 at 23:54
  • @ÓscarLópez The formula is n^2=1+3+5+(n+n-1), so if n=5, (n+n-1)= (5+5-1)= 9, meaning 5^2=1+3+5+7+9= 25. – Edward Wong Apr 14 '19 at 00:30
  • Thanks for the example, now the problem is clear. I took the liberty of formatting the code, notice the correct way to indent the code and close the parentheses, it'll make it easier to find bugs. Also, check my answer! – Óscar López Apr 14 '19 at 04:40

1 Answers1

2

The problem is that the procedure gets stuck in the the second if, never reaching the base case because of the way your conditions are structured. We should split the problem in two parts: one procedure for checking the cases when n <= 0 and the other for performing the loop in the general case.

Be aware that in a Scheme procedure, only the result of the last expression gets returned - the other expressions are executed for sure, but their results ignored. In the case of an if expression, structure it so it always has an "else" part. Having said that, this should work:

(define (aux n)
  (if (= n 1)
      1
      (+ (+ (+ n n) -1)
         (aux (+ n -1)))))

(define (square1 n)
  (if (= n 0)
      0
      (if (> n 0)
          (aux n)
          (aux (- n)))))

The above solution is correct, but not that idiomatic. We can do better!

  • The aux procedure should be internal to the main procedure, because it won't be used anywhere else
  • Instead of nesting ifs, it's nicer to use cond
  • We could use existing procedures for common task, like zero?, positive?, sub1
  • For efficiency, we should use tail recursion whenever possible

This is how a more idiomatic answer might look, it works the same as the first one:

(define (square1 n)
  (define (aux n acc)
    (if (= n 1)
        acc
        (aux (sub1 n) (+ acc (sub1 (+ n n))))))
  (cond ((zero? n) 0)
        ((positive? n) (aux n 1))
        (else (aux (- n) 1))))

Either way, it works as expected:

(square1 -4)
=> 16
(square1 -3)
=> 9
(square1 -2)
=> 4
(square1 -1)
=> 1
(square1  0)
=> 0
(square1  1)
=> 1
(square1  2)
=> 4
(square1  3)
=> 9
(square1  4)
=> 16
Óscar López
  • 232,561
  • 37
  • 312
  • 386