Recursion

[Gagless]

I am working on a recursive function that does multiplication so I don't have to use the * operator or loops.

What I'm stuck on right now is how to get it to produce negative products. I thought the code for positive products subtracted from 0 would work, but I get a stack overflow error.

( 0 - Number + ProductOfInts( Number, ( Multiplier - 1 ) ) );

[Duoas]

You're getting a stack overflow on windows? Are you on Windows 98 or something?

In any case, make sure you don't multiply too large of a number. It costs a lot more than you think in stack space to call a function, so it adds up fast.

The reason you are getting a positive number is that you only subtract the first addend, and add the remainder. You have to subtract all of them.

The best way to do that is this:

if (Multiplier < 0)
  {
  Number = -Number;
  Multiplier = -Multiplier;
  }

Now every time you add Number, you are adding a negative number; i.e. subtracting. If both terms were negative, you'll also properly get a positive result.

Hope this helps.

[n1337]

edit: how to delete a multiple post...

[n1337]

Just so you know, if you write *crafty* recursive code, a.k.a. tail recursive functions, your compiler should optimize for recursion and use less stack space (i.e. reuse stack space)...the equivalent of using a for or while loop. (At least, GCC optimizes for tail recursion...I would hope that *some* c++ compilers do so as well)

That is, if the function call is the last operation (and the calculations are done as parameters), then memory can be reused --> no intermediate build up of operations becuase in order to call the function, the function parameters will be evaluated first.

EDIT: I took out the examples because after posting this I got curious and started playing around in VC++...turns out my example was kind of useless (hard to see the distinction), and seems like VC++ doesn't optimize for recursion at all...moved over to GCC and was able to pump out way more recursive calls, but again I didn't see the optimization between the tail recursion and structurual recursion...Now I'll have to think about this...

Maybe worrying about optimized recursion is best left in Scheme. haha

[Duoas]

GCC has very limited support for tail recursion. The C++ standard does not require it, so if you want those kinds of optimizations you'll have to read your compiler's documentation on how to do it.

Iterative languages typically do not support tail recursion anyway... But that is usually a moot point since iterative and functional languages target a different application domain.

:-/ :)

[Gagless]

You're getting a stack overflow on windows? Are you on Windows 98 or something?

In any case, make sure you don't multiply too large of a number. It costs a lot more than you think in stack space to call a function, so it adds up fast.

The reason you are getting a positive number is that you only subtract the first addend, and add the remainder. You have to subtract all of them.

The best way to do that is this:

if (Multiplier < 0)
  {
  Number = -Number;
  Multiplier = -Multiplier;
  }

Now every time you add Number, you are adding a negative number; i.e. subtracting. If both terms were negative, you'll also properly get a positive result.

Hope this helps.

I apologize but I'm not understanding, wouldn't this produce a positive result? negative by negative = positive. And I'm still getting a stack overflow error. The integers I use for testing are 2 and -5.

[Gagless]

You're getting a stack overflow on windows? Are you on Windows 98 or something?

In any case, make sure you don't multiply too large of a number. It costs a lot more than you think in stack space to call a function, so it adds up fast.

The reason you are getting a positive number is that you only subtract the first addend, and add the remainder. You have to subtract all of them.

The best way to do that is this:

if (Multiplier < 0)
  {
  Number = -Number;
  Multiplier = -Multiplier;
  }

Now every time you add Number, you are adding a negative number; i.e. subtracting. If both terms were negative, you'll also properly get a positive result.

Hope this helps.

I apologize but I'm not understanding, wouldn't this produce a positive result? negative by negative = positive. And I'm still getting a stack overflow error. The integers I use for testing are 2 and -5.

[Duoas]

I apologize but I'm not understanding, wouldn't this produce a positive result? negative by negative = positive.

I think you need to reconsider you math.

In particular, remember the definition of multiplication: [b]a multiplied by b is a added to itself b times[/b] Now we'll have to use the associative property and distributive property (of multiplication over addition). In the following, [b]a[/b][I]n[/I] is to be understood as the nth term of a. A couple steps are skipped for brevity. -[B]b[/B] x [B]a[/B] = (-1 x [B]b[/B]) x [B]a[/B] = -1 x ([B]b[/B] x [B]a[/B]) = -1 x ([B]a[/B][I]1[/I] + [B]a[/B][I]2[/I] + ... + [B]a[/B][I](b-1)[/I] + [B]a[/B][I]b[/I]) = (-1 x [B]a[/B][I]1[/I]) + (-1 x [B]a[/B][I]2[/I]) + ... + (-1 x [B]a[/B][I](b-1)[/I]) + (-1 x [B]a[/B][I]b[/I]) = -[B]a[/B][I]1[/I] - [B]a[/B][I]2[/I] + ... - [B]a[/B][I](b-1)[/I] - [B]a[/B][I]b[/I] So, if we were to say b is 5 (as in, we are multiplying a by -2), we can substitute to get: -[B]a[/B] -[B]a[/B] -[B]a[/B] -[B]a[/B] -[B]a[/B] Suppose a is 2: -2 -2 -2 -2 -2 Suppose a is -2: -(-2) -(-2) -(-2) -(-2) -(-2) = 2 + 2 + 2 + 2 + 2

And I'm still getting a stack overflow error. The integers I use for testing are 2 and -5.

OK, that is odd. Let's see your code.

[Gagless]

#include<iostream>
#include "Tools.h"

using namespace std;

int ProductOfInts( int Number, int Multiplier );


int main()
{
	cout << ProductOfInts( 2, -5 );
	HoldScreen();
}

/////////////////////////////////////////////
// Multiplication without loops or * operator

int ProductOfInts( int Number, int Multiplier )
{

	// if the Multiplier is equal to -1, the product
	// is the difference of 0 and the Number
	if (Multiplier == -1 )
		return ( 0 - Number );
	
	// if the Multiplier is less than -1, the product
	// is the recursive forumla subtracted from zero.
	
	// This is what I thought it should be, but I get a
	// stack overflow error.
	/*
	if ( Multiplier < 0 )
		return ( 0 - Number + ProductOfInts( Number, (Multiplier - 1 ) );
	*/
	
        if ( Multiplier < 0 )
	Number = -Number;
	Multiplier = -Multiplier;
	

	// if the Multiplier is equal to 0, then
	// the product is equal to the Multiplier,
	// which is 0.
	if ( Multiplier == 0 )
		return Multiplier; 

	// if the Multiplier is equal to 1,
	// then the product is equal to the Number.
	if ( Multiplier == 1 )
		return Number;
	
	// if the Multiplier is greater than 1,
	// then the product is equal to the sum of
	// the number and the number( multiplied by 
	// one less than the multiplier )
		return Number + ProductOfInts( Number, ( Multiplier - 1 ) );
}

if the multiplier value is changed to a value less than zero I get that stack error.

[Duoas]

Yes, OK. Your routine should terminate when you hit one, not -1. (You've got it right for the last three clauses of your code -- the stuff handling the positive numbers.) The trick is what happens when things go negative.

It might help to visualize what is going on a couple of times.
The routine is (should be) defined to recurse as follows (what you have for positive numbers):

(mult a b) = (+ a (mult a (- b 1)))
(mult a 1) = a
(mult a 0) = 0

So for an example:

(mult 2 5)
= (+ 2 (mult 2 4))
= (+ 2 (+ 2 (mult 2 3)))
= (+ 2 (+ 2 (+ 2 (mult 2 2))))
= (+ 2 (+ 2 (+ 2 (+ 2 (mult 2 1)))))
= (+ 2 (+ 2 (+ 2 (+ 2 2))))
= (+ 2 (+ 2 (+ 2 4)))
= (+ 2 (+ 2 6))
= (+ 2 8)
= 10

And another:

(mult -2 5)
= (+ -2 (mult -2 4))
= (+ -2 (+ -2 (mult -2 3)))
= (+ -2 (+ -2 (+ -2 (mult -2 2))))
= (+ -2 (+ -2 (+ -2 (+ -2 (mult -2 1)))))
= (+ -2 (+ -2 (+ -2 (+ -2 -2))))
= (+ -2 (+ -2 (+ -2 -4)))
= (+ -2 (+ -2 -6))
= (+ -2 -8)
= -10

So far, so good. But what if b is negative. You can't subtract one from it and get closer to zero (hence your stack error). The trick, then, is to use the associative property to modify the numbers before any actual recursion happens. [B]a[/B] x -[B]b[/B] = [B]a[/B] x (-1 x [B]b[/B]) = ([B]a[/B] x -1) x [B]b[/B] = -[B]a[/B] x [B]b[/B] If a was positive, it is now negative. If a was negative, it is now positive. In either case, b is now positive. So we can modify the definition of the function thus:

(mult a b) = (+ a (mult a (- b 1)))
(mult a -b) = (mult -a b)
(mult a 1) = a
(mult a 0) = 0

In a more mathematical way of expressing it:

mult( a, b ) = | b = 0: 0
               | b = 1: a
               | b < 0: mult( -a, -b )
               | else: mult( a, b-1 )

The first two lines represent things you should test for first in your function, and the last represents the default case.

Think about it and I'm sure you'll get it. Hope this helps.

[Gagless]

I think I got it, thanks for your help.

[Gagless]

I think I got it, thanks for your help.