recursions in functions

[ishan]

hi guys,
i am a newbie and learning c++ currently.
i know functions and all the basic stuff.

I was recently given this problem and need a solution.

a triangle is inputted in the form of lower triangular matrix in a 2d array.
the matrix may contain negative numbers.
u have to find the maximum sum from all possible routes going top to bottom.
each time u can either move down or move diagonally bottom right.

eg.

2
4 5
100 -80 12
20 1400 99

here the maximum sum is 1327.

my teacher has recommended me to use recursions in functions.(where u call a function inside itself).

if u have any other logic that would do.

thanx in advance.


ishan.

[Ganon11]

I think you need to explain your problem more fully. Let me try to sort out the information you have given us:

You will have a 2D int matrix filled with values in a triangular pattern, like

x is relevant data
_ is 0 or unititialized - not accessed, irrelevant
 
x _ _ _
x x _ _
x x x _
x x x x

You want to find the path from top to bottom (moving only down a.k.a. array[0][0] to array[1][0] or moving down-and-right a.k.a. array[0][0] to array[1][1]) that results in the largest sum, and report that sum.

You want to use a recursive function to determine this.

Is all this correct? Is there any other information that might help us help you?

[gtg588n]

Also, complementing what Ganon11 said, if his interpretation is correct (which was my interpretation too), your example seems incorrect.

eg.

2
4 5
100 -80 12
20 1400 99

here the maximum sum is 1327.

Why can't you get:
2->4->100->1400, getting a sum of 1506, thus greater than 1327.

Why isn't this sequence valid?

[ishan]

sorry guys.
your interpretetion is correct.
the maximum sum is not what i mentioned.
i was just trying to show that sometimes having a negative value in your 'path' can also lead to maximum sum and thus u have to check all possible ways.

now can u guys help me with program.

[Ganon11]

I'm afraid that I don't understand the problem at all, then. Could you explain it in a little more detail so we could have an idea as to where to start?

[macklin01]

I think I would represent each path as a seqence of 0s and 1s. 0 represents straight down, and 1 represents down and to the right.

Think about your 4 x 4 example: the possible sequences are:

{0,0,0}
{0,0,1}
{0,1,0}
{0,1,1}
{1,0,0}
{1,0,1}
{1,1,1}

Do you see the natural ordering here? It's like going from 2^0 to 2^3-1 in binary. You simply iterate through all these paths to find the maximum number. No recursion is necessary. First, generate a sequence. Suppose we write it as

int Path[3];
Path[0] = 0;
Path[1] = 1;
Path[2] = 1;

In our example we go straight down, then diagonal twice. This path gives us the following matrix entries:

Matrix(0,0)
Matrix(1,0)
Matrix(2,1)

Notice that the notation even makes traversing the path easy to do in a very natural way. (Think of tracking a current row and current column, and each path step either increments or holds the column.) -- Paul

[ishan]

thanx paul.
ill be working on the solution.
BTW, how did this thing strike you????

[macklin01]

thanx paul.
ill be working on the solution.
BTW, how did this thing strike you????

I'm not sure what you meant by this.

At any rate, how did it turn out? -- Paul

[quiz123]

I'm afraid that I don't understand the problem at all, then. Could you explain it in a little more detail so we could have an idea as to where to start?

Hi I am new to recursions, my teacher wants me to use recursions to produce an out put 2,3,4,5,...N
this is the function prototype
int addint(int i, int N);
// hint: can use auxillary recursive function.
my thought process was:
assert (i<N);
if N = 0;
return 0;
i =2;
addone(i);
cout << i;
......
addone(int x){
return x+=1;
....
am i on the right track?my doubt is, recursion is to break the problem into smaller problems, i feel my code just calls another function repetitively to do the job.
what is your feedback?
thnx in advance.

[nmadct]

You're right that recursion helps by breaking up a problem into smaller steps. I've written a program that shows how to break up the counting problem into a recursive function.

Following the function that solves that problem, I've included a very similar function that counts through the series, but at each step it has the option of making the next number in the sequence the same value instead of increasing it by one.

I think you'll see that this ends up being very similar to the "triangle" problem. It ends up branching out into more paths of execution as it proceeds. The output isn't completely intuitive at first but I think if you follow the code it will become clear what it's showing.

At the end of each line, it prints the total that the series adds up to.

#include <iostream>
using namespace std;
 
void printseries(int start, int end);
void branchingseries(int start, int end);
 
int main(int argc, char **argv)
{
        printseries(2,8);
        branchingseries(2,8);
}
 
void printseries(int start, int end) {
        // don't do anything if this isn't an ascending series
        if (start > end)
                return;
        if (start == end) {
                // terminate recursion if we're at the end
                cout << end << endl;
                return;
        }
        // if in the middle of the series, print the
        // current item in the series and keep counting
        cout << start << ",";
        printseries(start+1, end);
}
 
void branchworker(int count, int limit, int start, int total)
{
        cout << start;
        if (count == limit)
        {
                // if we've reached the end, print
                // the end of the line and terminate recursion
                cout << ": " << (start+total) << endl;
                return;
        }
        cout << ','; // we're going on, so print our comma now
        branchworker(count+1, limit, start, total+start);
        cout << ',';
        branchworker(count+1, limit, start+1, total+start);
}
 
void branchingseries(int start, int end)
{
        // don't do anything if this isn't an ascending series
        if (start > end)
                return;
        branchworker(0, end-start, start, 0);
}