Write a program for difference equation in C

[Shervan360]

Hello,



I would like to write two programs to solve this difference equation, iteratively, and recursively.

I don't want to write programs for me. I am somewhat familiar with the C language.

I have trouble understanding the question. The question is vague to me.

Could you please give me an idea or a simple example?

Difference equation:

https://i.ibb.co/rMpp7YV/photo-2021-01-11-19-36-58.jpg


Thanks

[lastchance]

Start with a Fibonacci solver. Then use an extra precursor for each new point and change the weights.

Alternatively, if you want to store the values then create an array and loop the equation given in the question.

[Shervan360]

Thank you,

I wrote it iteratively, Is this true?

https://i.ibb.co/gS7Ygmc/Screenshot-2021-01-13-132351.jpg

#include <stdio.h>


int main()
{
	float y0, y1, y2, y3;
	printf("y0: ");
	scanf("%f", &y0);
	printf("y1: ");
	scanf("%f", &y1);
	printf("y2: ");
	scanf("%f: ", &y2);
	printf("N: ");
	int n; scanf("%d: ", &n);

	for (int i = 3; i <= n; i++)
	{
		y3 = 2 * y2 + y1 + 0.5 * y0;
		y0 = y1;
		y1 = y2;
		y2 = y3;
	}

	printf("%f", y3);


	return 0;
}

And recursive code is:

#include <stdio.h>

float y0; float y1; float y2;

float Diff(int n)
{
	if (n == 0)
		return y0;
	if (n == 1)
		return y1;
	if (n == 2)
		return y2;
	else
		return 2 * Diff(n - 1) + Diff(n - 2) + 0.5 * Diff(n - 3);

}

int main()
{
	printf_s("y0: ");
	scanf_s("%f", &y0);
	printf_s("y1: ");
	scanf_s("%f", &y1);
	printf_s("y2: ");
	scanf_s("%f: ", &y2);
	printf_s("N: ");
	int n; scanf_s("%d: ", &n);



	printf_s("%f", Diff(n));


	return 0;
}

[lastchance]

Your iterative code is OK. Here's another version (which stores the values).

#include <iostream>
#include <vector>
using namespace std;

vector<double> diff( double y0, double y1, double y2, int N )
{
   vector<double> F(N);
   F[0] = y0;   F[1] = y1;   F[2] = y2;
   for ( int i = 3; i < N; i++ ) F[i] = 2 * F[i-1] + F[i-2] + 0.5 * F[i-3];
   return F;
}

int main()
{
   double y0 = 0, y1 = 1, y2 = 2;
   int N = 20;
   vector<double> F = diff( y0, y1, y2, N );
   for ( int i = 0; i < N; i++ ) cout << i << ": " << F[i] << '\n';
}

Your recursive version doesn't compile for me because it uses non-standard functions.

However, if it did it would probably "work" for small n and blow the stack for larger n (because each function call will put another three recursive function calls on the stack and there will be exponential growth in the amount of stuff on the stack). You could either
(a) recurse like a loop; (which is cheating, but meets the constraints of the question); or
(b) memoise the values that you have already calculated so as not to evaluate them multiple times with recursive functions.

Iteration is OK for this problem, but recursion isn't.

[Shervan360]

Thank you for your answer. It is great.

The recursive method runs for me:

https://i.ibb.co/6BkqT7g/Screenshot-2021-01-13-142844.jpg

[lastchance]

Try your recursive code with y0=0, y1=1, y2=2 and ... n = 60.

We'll wait.

[Shervan360]

Unfortunately, it will take a long time. the recursive method works just for small n.

[lastchance]

The problem is that each call of the recursive function spawns several new calls, so (a) the amount on the stack grows exponentially and (b) you end up calculating exactly the same value a vast number of times.

The only way to avoid that is to memoise it (i.e. store what you have already calculated and not require it to spawn new function calls). But here it would be far better just to use the iterative loop than to use recursion.

[jonnin]

here is the 'letter of the law' recursive version. Its worse than the iterative version and the recursion does nothing but replace the iteration loop. It serves no purpose other than 'someone told me to make it recursive'. And you can't change N like this (that can be fixed, but its annoying -- if current N > size of the vector you update the size, and it would also need zeroed out if you use it more than once). Really the only point is that you can make things recursive, even when you should not...

vector<double> &diff( double y0, double y1, double y2, int N, int i = 2 )
{
   static vector<double> F(N);
   if(i == 2)
   {   
   F[0] = y0;   F[1] = y1;   F[2] = y2;
   diff(0,0,0,N, i+1);
   }
   else
   if(i<N)
   {   
   F[i] = 2 * F[i-1] + F[i-2] + 0.5 * F[i-3];
   diff(0,0,0,N,i+1);
   }   
   return F;
}

[lastchance]

Iteration in a loop would still be better! However, for recursion:

#include <iostream>
#include <vector>
#include <map>
using namespace std;

double diff( double y0, double y1, double y2, int n )
{
   static map<int,double> F;
   if ( !F.count(n) )             // If not previously calculated
   {
      switch ( n )
      {
         case 0:   F[n] = y0;   break;
         case 1:   F[n] = y1;   break;
         case 2:   F[n] = y2;   break;
         default:   F[n] = 2 * diff(y0,y1,y2,n-1) + diff(y0,y1,y2,n-2) + 0.5 * diff(y0,y1,y2,n-3);   // recursion
      }
   }   
   return F[n];
}

int main()
{
   double y0, y1, y2;
   int N;
   cout << "Input y0, y1, y2, N: ";   cin >> y0 >> y1 >> y2 >> N;
   cout << diff( y0, y1, y2, N ) << '\n';
}

Input y0, y1, y2, N: 0 1 2 60
1.66606e+23

[dhayden]

You can do it recursively without storing all the previous values. You only need the previous 3:

#include <stdio.h>

float y0;
float y1;
float y2;

// Recursive function to compute y[k] where
// y[n+3] = 2y[n+2] + y[n+1] + 0.5y[n] and y[0], y[1] and y[2] are given
// Rewrite that as y[k] = 2y[k-1] + y[k-2] + 0.5y[k-3]
// On input, y2=y[2], y1=y[1], y0=y[0].
// On output, y2=y[k], y1=y[k-1], y0=y[k-2]
float
iDiff(int k, float &y2, float &y1, float &y0)
{
    if (k == 2) {
	return y2;
    } else {
	iDiff(k-1, y2, y1, y0);
	// Now y2=y[k-1], y1=y[k-2] and y0=y[k-3]
	float result = 2*y2 + y1 + 0.5*y0;
	y0 = y1;
	y1 = y2;
	y2 = result;
	// Now y2=y[k], y1=y[k-1] and y0=y[k-2]
	return result;
    }
}

float Diff(int n)
{
    float y2=::y2,y1=::y1,y0=::y0; // to avoid changing the globals.
    return iDiff(n, y2,y1,y0);
}

float iterative(int n)
{
    float y3 = 0.0;
    for (int i = 3; i <= n; i++)
	{
	    y3 = 2 * y2 + y1 + 0.5 * y0;
	    y0 = y1;
	    y1 = y2;
	    y2 = y3;
	}
    return y3;
}

int
main()
{
    printf("y0: ");
    scanf("%f", &y0);
    printf("y1: ");
    scanf("%f", &y1);
    printf("y2: ");
    scanf("%f: ", &y2);
    printf("N: ");
    int n;
    scanf("%d: ", &n);

    printf("Recursive: %f\n", Diff(n));
    printf("Iterative: %f\n", iterative(n));

    return 0;
}

Input:

1 2 3 30

Output:

$ time ./foo < input
y0: y1: y2: N: Recursive: 392383168512.000000
Iterative: 392383168512.000000

real    0m0.038s
user    0m0.015s
sys     0m0.030s

[jonnin]

Much better! Even in this better written case, recursion isnt bringing anything to the table. My rule of thumb on recursion is that it has to be better in some way than iteration, or don't use it.

[dhayden]

My rule of thumb on recursion is that it has to be better in some way than iteration, or don't use it.

Very true!!!