Printable View
hello.
i need to write a program (function) which takes one argument (n)and returns the sum of an arithmetic such this:
(1+n^2)+(3+n^4)+(5+n^6)+.....((2n-1)+n^2n
oh and btw..it has to be a recursive function...and using of function libaries is not allowd. (such pow(),sqrt() etc...)
any idea?
10x
Sounds like a homework assignment. People here won't do your homework for you. If you need help, ask a specific question such as "What terminating condition should I use in my recursive function?" Just asking for ideas won't get you any help. Give it a legitimate try first, then come here with your questions.
its not homework...im cpp incomer,and im trying to practice things...Quote:
Originally Posted by Bob Davis
tried this without a success.
any info will be good...
As a side note, 6^12 as already about 2*10^9, which is quite under the limit of 32 bit integer. And anyway you should write it yourself, it's not difficult at all. Write looping solution first, then pack all but one loops into recurive call.
one problem....it has a logic i can increment the calling function by 2 everytime since
(1+n^2) + (3+n^4)....
is incremented by 2 everytime.
but my problem is here : how to power without using the pow function ????
This screams homework problem!
If I am wrong, then you won't mind me answering the question using different directions (i.e. avoiding recursion):
This series can be better broken up into two series:
1 + 3 + 5+ 7 + 9 + ... + (2n-1) [an arithmetic series]
n^2 + n^4 + n^6 + n^8 + ... n^2n [a geometric series]
Both series are very easily converted to expressions that require very few operations and no recursion. You can look up how to do this on MathWorld or in any good algebra book.
Anyway, if you are doing this just for learning, then there is an important lesson here to. Though brute force methods do work, there are often more efficient and less obvious solutions. Be open minded!
By the way, the sum of the arithmetic series is n^2.
The sum of the geometric series is n^2*(n^(2n) - 1)/(n^2 - 1)
Thus the total is n^2*(1 + (n^(2n) - 1)/(n^2 - 1))
That's basic math,Quote:
Originally Posted by DevGuy
n^m = n*n*n* ...... *n (m times)
well thats a nice way...10x
btw..how can i sum things in a recursive function??
i cant declare vars since they will be created all over again in each call...
For example, if you need to sum items of set {f(i)}, i=1..n, you can do in it cycle:The same sum can be represented the following way:Code:int sum=0;
for(i=1;i<=n;i++) sum+=f(i);
Note that the last line containing cycle is the same code as in the first variant with (n-1) instead of n. This can be used for recursion:Code:int sum=f(n);
for(i=1;i<=n-1;i++) sum+=f(i)
Code:int sum_first(int n){
if(n==0) return 0; // sum of no components is obviously zero!
return sum_first(n-1)+f(n); // f(1)+f(2)+...+f(n) == ( f(1)+f(2)+...+f(n-1) ) + f(n)
}
well i have a serious issue with these recursion thingy...
i cant make it )-:
Post your best attempt....
If you want to be a little clever, you can use so called loop invariants to calculate the power of some number:
Using correctness proofs, it can be shown that the above code will work for any value of base and exponent (subject to the storage of an int) without having to come up with elaborate test cases. You can probably get a recursive version without too much difficulty.Code:int pow(int base, int exponent)
{ int answer = 1;
while (exponent > 0)
{ if (exponent % 2 != 0) // exponent is odd number
{ answer *= base;
exponent--;
}
else // exponent is even
{ base *= base;
exponent /= 2;
}
}
return answer;
}
Now, on to your problem, this is considered a weak use of recursion, requiring almost no thinking at all, the solution is just the given math statement plus the result of its successors:
I didn't put in the terminating condition since I don't know for what values of n are defined.Code:int func(int n)
{ return (/* do the math */ ) + func(n - 1); }
Quote:
Originally Posted by TheCPUWizard
i dont have one,i cant belive this...i couldnt really understand how to do it...even tough i know how recursion works.
To use recursion you first need a recursive formulation of the problem. In such a formulation the next stage is defined in terms of the previous stage. When recursion is programmed the stage is represented by a function. To go to the next stage you pass the stage information in the form of function parameters. When you return from a stage you can pass information back in the form of the function return value.Quote:
Originally Posted by DevGuy
(1+n^2)+(3+n^4)+(5+n^6)+.....((2n-1)+n^2n
Say each term in this sum is (a + b). What is the term in the next stage (an + bn)?
an = a + 2
bn = b*n^2
The value of a stage is a + b, but what you want to return to a previos stage is this value plus the (to be calculated) value of the next stage. In this way, when the first stage is reached again it will contain the sum of all stage values.
All this in pseudocode,
Code:stage(a, b, n2, terms) { // stage
value = a + b; // value of this stage
terms = terms - 1; // one term less
if (term <= 0)
return value; // last stage
else
return value + stage(a+2, b*n2, n2, term); // value plus value of next stage
}
//
n = ....;
terms = .....; // number of terms in sum
n2 = n*n; // n^2
sum = stage(1, n2, n2, terms); // first stage