F(n) = 2 + 4 + 6 + ... 2n recursive func

Woops typo. Yes, I meant 2 not 1.

Yes, my last return statement is incorrect. Not sure what it should be. Use a factorial algorithm perhaps? I still get 0 for all answers though if I forget about using pass by reference. Unfortunately I have to figure out how to do it by reference though. :(

S G H (2638)

Can't you use a const reference?
If you can, just add "const" before "&".

Following that, plus indentation issues:


#include <iostream>

using namespace std;


int fn(int x);

int main()
{
    int number;

    cout << "Enter n for computing F(n);  ";
    cin >> number;

    cout << "F(" << number << ") = " << fn (number) << "\n? ";
  
    return 0;
}

int fn(int x)
{
    if (x == 1) // not number -- inside a function, use the argument value
    {
        return 2;
    }
    else if (x == 0)
    {
        return 0;
    }
    else
    {
        return fn(2*(x-1)) + fn(2*(x-2)) + fn(2*x);  // this line is wrong
    }
}

Remember, your algorithm is:

    2*x + 2*(x-1) + 2*(x-2) + ... + 2*1

The last term is handled by your base case (and you also have a nice base case in there for x==0).

So your return statement needs to calculate the current term (the first item in the list, right?) and add the result of calculating the function over the remainder of the list.

You'll have to think hard about that... (recursion is tricky!)

Remember, if I can do something to the first item in a list and the remainder of a list, I can do it to the whole list. For example, given a list

    { 3, 7, 2, 1, 4 }

and a function that sums it, I can calculate the sum as:

    sum( { 3, 7, 2, 1, 4 } ) = 3 + sum( { 7, 2, 1, 4 } )

Recursion kicks in, and in the recursive part, our list is { 7, 2, 1, 4 }. Calculating the sum of that is:

    sum( { 7, 2, 1, 4 } ) = 7 + sum( { 2, 1, 4 } )

and so on, until we hit our base case:

    sum( { 4 } ) = 4

Your list function works the same way, except:

    1 Your list is { x, x-1, x-2, ..., 1 }

    2 You multiply each element of the list by 2 before adding it.

Hope this helps.

Hmmm, ok. I think that makes sense to me but I'm confused about how to write the algorithm to include the part of the equation where the ... is (2*x + 2*(x-1) + 2*(x-2) + ... + 2*1). Writing algorithms confuses me worse than writing the actual code. :(

Do I do something like sum = 0; sum = sum + 2*x + 2*(x-1) + 2*(x-2)?

Think about the recursion pattern.

a₀ = 0;
a_n = a_{n - 1} + 2

So say we have n = 3 ( like your example)

Then it is:
a₁ = 0 + 2 = 2
a₂ = 2 + 2 = 4
a₃ = 4 + 2 = 6

Then to find the sum the formula is:

s_n = n/2( a₁ + a_n )

So with your example sum(3) =
3/2( 2 + 6 ) =
3/2( 8 ) =
24 / 2 =
12

I'm sorry. I'm really confused now. I understand the first part of your explanation but where in the world did the n/2 come from?? :(

I'm just not getting how to translate this all into the code that I need. :( I'm really getting frustrated.

Last edited on

...

Maybe he was asleep. I post silly things when I'm asleep too.

Don't feel bad. This is a difficult thing to wrap your brain around. The principle is this:

A list can be considered as the first item in a list and the rest of the list.

{ 5, 4, 3, 2, 1 } a list

5, { 4, 3, 2, 1 } first item, rest of list

Notice that the rest of the list is itself a list. Which means, of course, we can use our funny way of looking at it again.

Your list is given by the numbers { x, x-1, x-2, x-3, ..., 3, 2, 1 }. You can actually see the list when you print it out:

void print_my_list(int x)
{
    if (x==1)
    {
        cout << "1\n";
    }
    else
    {
        cout << x << ", ";
        print_my_list(x-1);
    }
}

int main()
{
    print_my_list(5);
}

5, 4, 3, 2, 1

The above function can be seen as:

    • if x == 1:
        • print x (because the list is only a single element, and we are done after printing it)
    • else:
        • print x
        • print the remainder of the list

Let's see if we can modify that to sum the elements of the list. (We'll get to that multiplication by two in a second.)

The elements are now related by adding them:

     x + (x-1) + (x-2) + ... + 3 + 2 + 1

Instead of printing them, you are going to get the first element and add it to the remainder of the list's sum. See the recursion there? The first part remains the same:

    • if (x == 1):
        • return 1 (because the sum of a single thing is itself)
    • else:
        • return x + sum of remainder of list beginning with (x-1)

See if you can write code that does just that. Once you do, then you only need to throw in that multiplication by two. The trick to remember is that, even though it is true that you could factor it out, the recursive mechanism we have set up cannot do it that way, since the function does not know whether it has the beginning of the entire list or just a sublist. So you are stuck multiplying individual elements.

fn(0) == 0
fn(1) == 2 right? Because 2*1 == 2?
fn(2) == 2*2 + 2*1
fn(3) == 2*3 + 2*2 + 2*1

Hope this helps.

for his example he showed 2 , 4 , 6 which would imply it was an arithmetic sequence then I just converted it to a recursion which should yield the same results for a_n and the sum of arithmetic equations is n( a₁ + a_n )/ 2 or the method I mentioned earlier same thing doesn't matter if u multiply by n then divide by 2 or do n/2 then multiply.

I assumed he was trying to achieve:
a_n = 2n

so when you convert the same equation to recursion it should yield the same sum equation.

Like I was trying to say...
You are trying to find the sum doing it the hard way...
s_n = a₁ + a₂ + a₃ + a_n + ...

The easy way to rewrite this arithmetic sum is:
s_n = n/2(a₁ + a_n

http://www.purplemath.com/modules/series4.htm

http://www.regentsprep.org/regents/math/algtrig/ATP2/ArithSeq.htm

The second link about 1/3 down the page it has the formula written nicely without the sigma (sum symbol) unfortunately and I would have put in my equations but too lazy to open character map. but s_n is same as sigma.

#include <iostream>

int recursive_an( int n )
{
	if( n > 0 )
		return( 2 + recursive_an(n-1) );
	else
		return( 0 ); //a0 = 0
}

int arithmetic_an( int n )
{
	return( 2 * n );
}

int arithmetic_sum( int n )
{
	return( ( n * ( arithmetic_an( 1 ) + arithmetic_an( n ) ) ) / 2 ); //integer division but it should
	//be fine since d == 2 everything must be divisible by 2
}

int recursive_sum( int n ) //with an arithmetic sequence
{
	return( ( n * ( recursive_an( 1 ) + recursive_an( n ) ) ) / 2 );
}

int main()
{
	const int n = 4; //what you picked in example:
	
	std::cout << "Arithmic sum:  " << arithmetic_sum( n ) << std::endl; //2 + 4 + 6 + 8 == 20
	std::cout << "Recursive sum: " << recursive_sum( n ) << std::endl;  //2 + 4 + 6 + 8 == 20
	return 0;
}

*Edit

I never answered question where n/2 came from..basically you add the first and last element then divide by 2 to get the mean then multiply that by n elements and it will result in the sum of all elements ( in arithmetic ).

here is a good link that explains:
http://www.mathsisfun.com/algebra/sequences-sums-arithmetic.html (near bottom)

Last edited on

You are doing more work than you need. Essentially you've plugged an n/n in there. Don't do that.

The sequence factors quite simply to 2(n + n-1 + ... + 2 + 1).

In order to do it that way, you must have a non-recursive top function:

def f_helper( x ):
  if (x == 1) return x
  else return x + f_helper( x-1 )

def f( x )
  return 2 * f_helper( x )

Ohhh ok. I think I sort of understand. Thank you Duoas and Giblit!! I appreciate your patient explanations. The links to arithmetic series also greatly helped me wrap my brain around this crazy stuff!

So in the formula: sum = n(a1 + an)/2, the "an" is where you're putting the recursive function. The a1 is basically going to be "2" no matter what number you put in for n because it's always the first number in the list to sum for that particular F(n) formula. Then the "an" (recursion part) is = to the other formula a1 + (n-1)d and it will continue to call itself until "n" gets to "1". "d" is the space or difference between the numbers in the sequence. So if the sequence was F(n) = 1 + 4 + 7 +10... +3n then d would be = to 3 and you'd use the other formulas in the same way?

LIGHT BULB over head....I think!! :)

Um ok, how would I go about passing this by reference? Been trying a few things but keep getting a "undefined reference to..." and it lists my function names after that. Why can't you just put the int & in your function definition and go from there? I ask this because all the examples I've looked at seem to do it that way and then compile correctly.

Yeah d is the rate of change

Say we had this sequence

7 12 17 22 ...

Then the equation would be

is it arithmetic?
12 - 7 = 5
17 - 12 = 5
22 - 17 = 5

yes , all rates of change are the same.

a_n = a₁ + d(n - 1)
a_n = 7 + 5( n - 1)
a_n = 7 + 5n - 5
a_n = 2 + 5n

then the sum of n would be

s_n = n/2( a₁ + a_n )

so lets say we want to find the sum of n = 5

then it would be s₅ = 5 * ( 7 + 2 + 5(5) ) / 2 = 5 * ( 9 + 25 ) / 2 = 5 * ( 34 ) / 2 = 170 / 2 = 85

Hambone (149)

Just for a general FYI the general formula can be written as (n)(n+1)

What if you need or want to run larger numbers? I tried a few larger digit numbers and it locks up the program. I've tried changing to double and long and all that but didn't help.

How large of numbers are we talking?

Five to Six digits. Example: 123569

Last edited on

A long int should be able to handle that easily.

But your call stack cannot.

Unless you make your function tail-recursive. (It currently is not.)