Recursion

[Daler Isoev]

Such kind of problem:


A1=1000*0.2

A2=(1000-A1)*0.2

A3=(1000-A1-A2)*0.2

................................

An=(1000-A1-A2-.....-An)*0.2
Need to solve this expression with using a recursion.
I have some ideas but probably they not working.

  #include <iostream>
using namespace std;
double f(double n){
if(n<=0){return 0.2;}
return (1000-f(n-1))*0.2;
}
int main()
{
	int n;
	cout <<"Enter n: ";
	cin >>n;
    cout <<f(n) << endl;
    return 0;
}

please help with solving.

[abhishekm71]

one solution that you can try (i don't know if its accurate):

#include <iostream>
using namespace std;

double f(int n) {
  double sum = 1000*0.2;
  for (int i=0; i<n; i++)
    sum -= f(i)*0.2;
  return sum;
}

int main()
{
  int n;
  cout <<"Enter n: ";
  cin >>n;
  cout << f( n ) << endl;
  return 0;
}

EDIT: i and n should be int

[ajuzoo]

try this...

#include <iostream>
#include<cmath>

using namespace std;

int main()
{
	int n,i,j;
	double sum=1000,b;
	cout<<"recursion calculation \n";
	cout<<"enter maximum recursion:";
	cin>> n;

	double a[n];
	a[0]=0;

	for(i=1;i<=n;i++)
	{
		for(j=0;j<=i-1;j++)
		{
			sum-=a[j];

		}
		b=sum*0.2;
		a[i]=b;
		cout<<"step-"<<i<<"  "<<a[i]<<"\n\n";
		sum=1000;
	}
}

[giblit]

no the problem is that you have if it is less than equal to 0 do something..it will repeat for ever. You should read the recursion section on this site http://www.cplusplus.com/doc/tutorial/functions2/

But anyways it would be something like this

double recursion( double n )
{
    if( n > 0.00001 ) return( ( 1000 - n ) * .2 - recursion( n - 1 ); //.00001 because it is a double and 0 could really be .000000000000001 and not 0.
    return( 1 ); //if n is 0 we return 1.
}

I think this is what you are trying to do but I could be wrong. It is hard to tell because I have no idea what a1 a2 and a3 are. I just assumed the were the previous values of 1000 - n * .2

Actually no my solution will not work can you please explain what a1, a2, and a3 are? Are they all the numbers greater than 0?

[abhishekm71]

The solution is given in the problem itself:
f(0) = 1000*0.2
f(1) = ( 1000 - f(0) ) * 0.2
f(2) = ( 1000 - f(1) - f(0) ) * 0.2
...
f(n) = ( 1000 - ( f(0) + f(1) + .... + f(n-1) ) ) * 0.2

[giblit]

After investigating your "formula" I noticed all it is doing is starting with 1000 then each time you call the function it divides by 2.
n = 2 would mean 1000 / 2 / 2 = 1000/4 = 250.
n = 4 would mean 1000 / 2 / 2 / 2 / 2 = 1000 / 8 = 62.5

So lets simplify your formula from
f(n) = (1000 - f( 0 ) - f( 1 ) - f( n ) ) * .2
to something more like this
f(n) = 1000 / ( 2n )

We can then code it like this

double function( int n )
{
    return( 1000 / ( 2*n ) ); //I see no point in using recursion.
}

*forgot a parenthesis.

[abhishekm71]

Please check again.
f(0) = 1000*0.2 = 200
f(1) = (1000 - f(0)) * 0.2 = 160
f(2) = (1000 - f(0) - f(1)) * 0.2 = 128

The answers are not coming to be 500,250,125,62.5.

[giblit]

Oh sorry I thought it said /2 miss read it.
That's an easy fix.
The new formula would be:
( 1000 * .2 ) * .8^( n - 1 )
or
200 * .8^(n-1)
so we could write that like this

double function( int n )
{
    return( 200 * pow( .8 , n - 1 );
}

*edit I am too lazy to come up with a recursion function. but it'd probably just multiply a static number by .8 each time the recursion happens.

[Smac89]

Here is what I have, but it does it in the form:

f(0) = 1000*0.2 = 200
f(1) = (1000 - f(0)) * 0.2 = 160
f(2) = (1000 - f(1) - f(0)) * 0.2 = 168
f(3) = (1000 - f(2) - f(1) - f(0)) * 0.2 = 166.4

Someone can find a way to make it do the recursion the other way i.e. f(0)-f(1)-f(2)-...f(n-1)

double recurrsive( int n ) {
	if ( n == 0 )
		return ( 1000 * 0.2 );
	return ( 1000 - recurrsive (n - 1) ) * 0.2;
}

[giblit]

You're not returning the *.2 for the final result. By the way it is "recursive" not "recurrsive." Also I think using recursive for something like this is a waste. Might as well just put 200 * pow( .8 , n - 1 ) and get the answer that way. I think it's better to use logic and go the easy way not the hard way. Also I think if you go the easy way it will compile a lot faster than using recursion.

[Smac89]

Nice! couldn't have come up with that formula myself

[Daler Isoev]

TNX ^^ guys. And special tnx to giblit.))