How to determine the sum of the squares of two numbers using a recursive method?

[flyingcurry]

The task is to use a recursive algorithm to determine the sum of two numbers n1 and n2.

I just keep on returning to using the formula n1*n1 +n2*n2

The part which I have questions is I don't get how to do this in a recursive way.

Thanks!

[cale.macdonald]

Just by looking at the question, why would you want to do recursion for that? It would be much easier just to do in a method using Math.pow and adding the results.

[kramerd]

There are 2 key ideas in recursive algorithms. The first is the problem must be something that can be broken down into simpler steps in an iterative manner. The second is the iteration must have a well defined stopping point. Factorial is a common example because it has a "natural" recursive solution. I.e., 5! = 5 * 4!, 4! = 4 * 3!, 3! = 3 * 2!, 2! = 2 * 1!, 1! = 1. So breaking the problem into simpler steps becomes n! = n * (n-1)!, and the stopping point is 1! = 1.

Understanding that recursive solutions are not particularly efficient (usually a loop performs better, at least in Java), both multiplication and addition problems can have recursive solutions. You just have to think about a simpler operation.

Multiplication can be accomplished by repeating addition, and Addition can be solved by repeatedly adding 1. The latter doesn't eliminate the addition operation, but it is simpler to just add 1, and this can be done using recursion.

[flyingcurry]

Just by looking at the question, why would you want to do recursion for that?

You just have to think about a simpler operation.

Thanks! It turns out that the question meant add all the sums of all the squares of the numbers from n1 to n2, so n1=2 n2=4 would give 29 as 4+9+16=29

Below is my code, it works fine:)

public static int sumSquares (int n1, int n2)
	{

		if (n1==n2)
			return n1*n2;

		return n1* n1 + sumSquares(n1+1, n2);

	}

[JamesCherrill]

One small suggestion:
This code will crash and burn horribly if presented with parameters like (3,2) or, more subtly, (-2,-3).
A simple replacement of the == on line 4 with a >= will protect against these nastys, as will the even simpler replacement of lines 4,5 with
if (n1>n2) return 0;

[flyingcurry]

One small suggestion:
This code will crash and burn horribly if presented with parameters like (3,2) or, more subtly, (-2,-3).
A simple replacement of the == on line 4 with a >= will protect against these nastys, as will the even simpler replacement of lines 4,5 with
if (n1>n2) return 0;

Thanks, it did crash and burn.
So I changed my code

public static int sumSquares (int m, int n)
	{

		if (m==n)
			return m*n;
		if (m>n)
			return 0;

		return m* m + sumSquares(m+1, n);

	}

[JamesCherrill]

If you have >= on line 6 you don't need lines 4,5 - just remove them and it will just recurse one more time and give the right result. I'm a great believer that the simplest code is usually the best.

[flyingcurry]

If you have >= on line 6 you don't need lines 4,5 - just remove them and it will just recurse one more time and give the right result. I'm a great believer that the simplest code is usually the best.

What does it mean by recurse one more time? Because when i take out line 4,5 and do >= for line 6, it just gives me 0 even if the two numbers are equal, and for some of the numbers like m=1, n=2, it gives me wrong results like three.

[JamesCherrill]

Oh, very sorry, small mistake in my last post. It was right with just the > on line 6. This version is short & works:

public static int sumSquares (int m, int n) {
      if (m>n) return 0;
      return m* m + sumSquares(m+1, n);
   }

My apologies.

[flyingcurry]

Oh, very sorry, small mistake in my last post. It was right with just the > on line 6. This version is short & works:

public static int sumSquares (int m, int n) {
      if (m>n) return 0;
      return m* m + sumSquares(m+1, n);
   }

My apologies.

Thanks! I see, so it works even if m and n are equal, it does the method again and does m*m+ sumSquares(m+1,n), which in this case will just give 0, so we get m*m.
The code is much simpler and the time complexity is more efficient!