Recursion Question

[toklo]

I've spent hours trying to code this with little progress. Recursion is tough to wrap my head around. Basically I need to output the first six terms of an equation to a file. The terms themselves are objects of type Complex with a real and imaginary part (e.g 4+6i). I also have a class that holds a vector of these Complex objects called ComplexVector. All of the operators have been overloaded, so that's not the problem. Let's call this the formula I need to output the first six terms...

f(n+1) = [(2+4i)n/(7+5n^2i)] * f(n)
with f(1) = 1+1i

So I'm thinking I need a void recursion function, but don't know how they actual recursion plays into that. Here is what I have so far:

  void recursive_equation(int numofseq) {
    std::ofstream out;
    out.open("ComplexSequence.txt");
    ComplexVector display;
    int n=0;
    while (n<numofseq) {
        if(n==0) {
            display.add_to_vector(Complex(1,1));
            break;
        } else {
            // what goes here? How do I implement the formula/recursion?
        }
    }
    
    out << display;
    out.close();
    
}

Assuming I put in recursive_equation(6) to get the first six terms. Also, I was going to count up and increment n by 1 somewhere in the while loop. Am I even approaching this right? Thanks for the help.

[kingkush]

Just to clarify a recursive function continuously calls itself until a "base case" has been met. For example lets say you wanted to count down from N. There might be some errors as i did not use a compiler but thats a simple function demonstrating recursion. Hopefully it'll help you understand recursion.

void countDown( int n )
{
     if(n == 0) //Base case to end recursive call
     {
       cout << n << "Blast off!" << endl;
     }
     else //If recursive call is not met
     {
       cout << n << endl;
       countDown(n-1) //Call function again (recursive call) but subtract 1 from n
     }
}

[JLBorges]

Something like this, perhaps:

#include <iostream>
#include <vector>
#include <complex>

using namespace  std::literals::complex_literals ;

std::complex<double> coeff( unsigned int n )
{
    if( n == 0 ) return 0 ; // domain error: undefined

    else if( n == 1 ) return { 1.0 + 1.0i }; // f(1) = 1+1i

    // f(n+1) = [(2+4i)n/(7+5n^2i)] * f(n), coeff = [(2+4i)n/(7+5n^2i)]
    // f(n) = [(2+4i)(n-1)/(7+5(n-1)^2i)] * f(n-1), coeff = [(2+4i)(n-1)/(7+5(n-1)^2i)]
    else return ( 2.0 + 4.0i ) * double(n-1) / 7.0 + 5.0 * ( std::pow( n-1, 2.0i ) ) ;
}

std::complex<double> fn( unsigned int n )
{
    if( n < 2 ) return coeff(n) ;

    // f(n) = coeff(n) * f(n-1)
    else return coeff(n) * fn(n-1) ;
}

std::vector< std::complex<double> > make_terms( unsigned int n )
{
    if( n == 0 ) return {} ;

    else if( n == 1 ) return { fn(1) };

    else
    {
        auto terms = make_terms(n-1) ; // terms up to n-1
        const auto& prev_term = terms.back() ; // fn(n-1)
        const auto this_term = coeff(n) * prev_term ; // f(n) = coeff(n) * f(n-1)
        terms.push_back(this_term) ; // add the nth term
        return terms ;
    }
}

int main()
{
    for( auto cmplx : make_terms(8) ) std::cout << cmplx << '\n' ;
}

http://coliru.stacked-crooked.com/a/853435df53355b0a

[lastchance]

Can't you just use a simple loop?

It's a "recursive formula" in the mathematical sense, but that doesn't mean you need to use a "recursive function" in the computer-programming sense.

#include <iostream>
#include <iomanip>
#include <complex>
using namespace std;

void mySequence( int num, complex<double> z );
void write( ostream &strm, int n, complex<double> z );

//======================================================================

int main()
{
   complex<double> z( 1.0, 1.0 );
   int num = 6;
   mySequence( num, z );
}

//======================================================================

void mySequence( int num, complex<double> f )
{
   write( cout, 1, f );
   for ( int n = 1; n < num; n++ )
   {
      f *= complex<double>( 2.0 * n, 4.0 * n ) / complex<double>( 7.0, 5.0 * n * n );
      write( cout, n + 1, f );
   }
}

//======================================================================

void write( ostream &strm, int n, complex<double> z )
{
   #define SP << " " << setw( 15 ) <<
   strm SP n SP z.real() SP z.imag() << endl;
}

               1               1               1
               2        0.216216        0.702703
               3        0.128092         0.28267
               4       0.0612953       0.0678346
               5        0.018252      0.00903443
               6       0.0036325     0.000188769

If you feel that you must put your sequence in a vector then you can use

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

#define cmplx complex<double>

vector<cmplx > mySequence( int num, cmplx f );
cmplx multiplier( int n );
void write( ostream &strm, int n, cmplx z );

//======================================================================

int main()
{
   const cmplx z( 1.0, 1.0 );
   const int num = 6;

   vector<cmplx > seq = mySequence( num, z );
   for ( int n = 1; n <= num; n++ ) write( cout, n, seq[n] );
}

//======================================================================

vector<cmplx > mySequence( int num, cmplx f )
{
   vector<cmplx > seq( num + 1 );      // to tie up with numbering, sequence[0] is not used
   seq[1] = f;
   for ( int n = 1; n < num; n++ ) seq[n+1] = multiplier( n ) * seq[n];
   return seq;
}

//======================================================================

cmplx multiplier( int n )
{
   return cmplx( 2.0 * n, 4.0 * n ) / cmplx( 7.0, 5.0 * n * n );
}

//======================================================================

void write( ostream &strm, int n, cmplx z )
{
   #define SP << " " << setw( 15 ) <<
   strm SP n SP z.real() SP z.imag() << endl;
}

//====================================================================== 

Please note that, due to the way that you have typed it, there are some differences of opinion as to what the multiplier is in your recursion formula; you will need to check it.

[toklo]

Thanks for the answers guys, but I don't find them exactly useful. I realize I could probably do this without recursion but I need to use recursion as instructed. I'd prefer it to be one function without all the other extras. And where does the output to file come in? Thank you.

[lastchance]

need to use recursion as instructed

Perhaps you could cite your actual instructions.

one function without all the other extras

Why? There isn't anything that is unused in any of the codes.

where does the output to file come in?

Replace any occurrence of the cout stream by whatever you have decided to call the file stream.

[toklo]

Ok, let me simplify this a little. Let's say I just want to return the n'th complex number of the equation. Why isn't this working?

Complex get_nth_term(int term) {
    int n=0;
    Complex b1;
    Complex b2;
    while (n<term) {
        if(n==0) {
            b1 = Complex(1,1);
            n++;
        } else {
            b2 = Complex((2*n),(3*n));
            b2 = b2/Complex(7,5*n*n);
            b2 = b2*get_nth_term(n-1);
            n++;
        }
    }
    if (term>1)
        return b2;
    else
        return b1;
}

[mbozzi]

Try something like this:

std::complex<double> f(int n) { 
    using c = std::complex<double>;
    if (n < 1) throw std::domain_error{"out of bounds"};

    auto result = n == 1? c{1.0, 1.0}
                        : (c{2.0*n, 4.0*n} / c{7.0, 5.0*n*n}) * f(n - 1);
    // std::cout << "f(" << n << ") = " << result << '\n';
    return result;
}

[lastchance]

Let's say I just want to return the n'th complex number of the equation. Why isn't this working?

You are trying to do a loop AND do a recursion. You need to make your mind up which.

If you want JUST the nth term in the equation then do a recursion (and @mbozzi has given you a very good example of this - must try out that using variant myself some time).

If you want a WHOLE SEQUENCE of terms then write them out (either to screen or to file) one by one as you find them - it would not be a good idea to keep going back to the beginning to restart a recursion from 1 every time you wanted a new term.

And your complex number on your line 10 is 2n+3ni, whereas your original specification said 2n+4ni ... so which is it?

[toklo]

Well I was going to return just the n'th term, then write another function to print out f(1), f(2), f(3)...f(6). So just use recursion I guess. I can't use the <complex> library, so while that may be the best way to do it, it's not available to me. And it is 2n+4ni. Typo by me.

[mbozzi]

I can't use the <complex> library, so while that may be the best way to do it, it's not available to me

It doesn't matter if you use std::complex or not. The logic is still the same.

write another function to print out f(1), f(2), f(3)...f(6).

As lastchance indicates, don't settle for O(n^2) when you could have O(n)

http://coliru.stacked-crooked.com/a/c429530e6dace3d2

[toklo]

I mean I can't use the 'throw' and 'auto' statements, wherever they came from.

[toklo]

I think I'm getting closer, removed the loops. Still not quite working though. The last else is if n=6, which is what I would input as num when calling the function. Then it should cout the vector (operator already overloaded). I may be overthinking things

Complex recursive_equation(int num) {
    ComplexVector visual;
    Complex b1, bn, b6;
    int n=num;
    if (n==1) {
        b1 = Complex(1,1);
        visual.add_to_vector(b1);
        return b1;
    } else if(n<6) {
        bn = Complex((2*n),(3*n));
        bn = bn/Complex(7,5*n*n);
        bn = bn*recursive_equation(n-1);
        visual.add_to_vector(bn);
        return bn;
    } else {
        b6 = Complex((2*n),(3*n));
        b6 = b6/Complex(7,5*n*n);
        b6 = b6*recursive_equation(n-1);
        visual.add_to_vector(b6);
        std::cout << visual << std::endl;
        return b6;
    }
}

[lastchance]

There is nothing special about 6 - it is just the last number in your sequence. It will be the value of num in the function call; you don't need the last else{}.

I have absolutely no idea why you need the extra ComplexVector.


You must be very careful with whether it is n, n-1 or n+1 in your recursion formula.
Your original post (I'm having to assume that was correct) said
f(n+1) = [ (2n+4n i) / (7+5n² i) ] * f(n)
(and I coded this directly in my earlier non-recursive code).

This is equivalent to (on replacing n by n-1):
f(n) = [ (2(n-1)+4(n-1) i) / (7+5(n-1)² i) ] * f(n-1)
which it needs to be written as for the correct recursion. This is what I have coded below.

At the moment output goes to stream cout. If you want any other then, with a recursive code, you would have to pass the stream reference as a function argument (as @mbozzi does in the Coliru link) or make it a global variable.

This is the nearest attempt I can get to your function. Since you won't tell us your original problem we are having to second-guess it from non-working code. The code below produces the same numbers (less prettily formatted) as my earlier non-recursive code.

Our codes show just ideas for you to consider. You will have to write your own code for your own particular problem. I'll stand by my original contention that recursive functions just don't seem right for this problem.

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

#define Complex complex<double>        // so that I can try to mimic your classes


Complex recursive_equation( int n )
{
   Complex b;
   if ( n == 1 )
   {
      b = Complex( 1.0, 1.0 );
   }
   else
   {
      b = Complex( 2.0*(n-1), 4.0*(n-1) ) / Complex ( 7.0 , 5.0*(n-1)*(n-1) );      // BE CAREFUL!!! n -> n-1
      b = b * recursive_equation( n - 1 );
   }
   cout << b << endl;
   return b;
}



int main()
{
   recursive_equation( 6 );
}

(1,1)
(0.216216,0.702703)
(0.128092,0.28267)
(0.0612953,0.0678346)
(0.018252,0.00903443)
(0.0036325,0.000188769)

[toklo]

Thank you. Figured it out.