Solved

C++ recusion

Posted on 2012-03-25
19
337 Views
Last Modified: 2012-03-25
Hi I am trying to write a recursive function that adds an array of integers. When I run this it actually crashes the console window so I'm guessing I must be doing something wrong to create a stack overflow? Here is the main program with the function.

#include <iostream>

using namespace std;

int sumOfElements(const int arr[], int size);

int main()
{
    int answer;
    int arrSize;
    cout << "how many numbers do you want to add" << endl;
    cin >> arrSize;
    int num[arrSize];
    for (int i = 0; i < arrSize; i++)
    {
        cout << "Enter number " << i + 1 << ": "; 
        cin >> num[i];
    }
    answer = sumOfElements(num,arrSize);
    cout << "The sum of the numbers entered is: " << answer << endl; 
    return 0;
}


int sumOfElements(const int arr[], int size)
{   
    int sum = arr[0];
    if (size == 1) 
        return sum;
    else
        return sum+= sumOfElements(arr, size + 1);
            
}

Open in new window

0
Comment
Question by:Dmon443
  • 9
  • 7
  • 3
19 Comments
 
LVL 31

Expert Comment

by:farzanj
ID: 37762773
One important thing in recursive programming is a valid stopping criteria--something that you are sure will always reach.  Your stopping criterion is size == 1.  While you are adding 1 to size for passing the next function.  I don't see how size value will ever converge to 1.  It so appears that it will keep on increasing so it will keep calling functions and will never get a chance to back track to the caller function.
0
 

Author Comment

by:Dmon443
ID: 37762798
ok now my second attempt with the help of your advice seems to be almost working but for some numbers it is not working eg if I add 5 numbers together 1 2 3 4 5 it throws out 5 as the answer and if I put them the opposite way 5 4 3 2 1 it throws out 25. Sometimes it works fine eg if I put 4 numbers 4 4 4 4 it gives the correct answer 16.

#include <iostream>

using namespace std;

int sumOfElements(const int arr[], int size, int sum);

int main()
{
    int answer;
    int arrSize;
    int sum = 0;
    cout << "how many numbers do you want to add" << endl;
    cin >> arrSize;
    int num[arrSize];
    for (int i = 0; i < arrSize; i++)
    {
        cout << "Enter number " << i + 1 << ": "; 
        cin >> num[i];
    }
    sum = num[0];
    answer = sumOfElements(num,arrSize, sum);
    cout << "The sum of the numbers entered is: " << answer << endl; 
    return 0;
}


int sumOfElements(const int arr[], int size, int sum)
{   
    if (size == 1) 
        return sum;
    else
        return sum+= sumOfElements(arr, size - 1, sum);
            
}

Open in new window

0
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 37762948
Where are you actually adding elements of the array? I don't see you indexing the array anywhere.
0
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 37762954
P.S.

Think about the results you are getting and the numbers you are entering. Do you see any correlation in the fact that whenever you enter n identical numbers, you get a result that is n * [the number]?  Why is that?
0
 
LVL 31

Expert Comment

by:farzanj
ID: 37762964
In recursive addition (or any recursive operations) all the work should be done in the recursive function which in your case is:

int sumOfElements(const int arr[], int size, int sum)
{  
    if (size == 1)
        return sum;
    else
        return sum+= sumOfElements(arr, size - 1, sum);
           
}

If you are trying to add elements of array, you should be passing only the index NOT sum and the it should return value of that element like

return arr[index];
instead of return sum

The backtracking part should work fine now as you are doing size - 1 so size value will eventually reach value 1.
0
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 37762982
If you are trying to add elements of array, you should be passing only the index NOT sum and the it should return value of that element like

return arr[index];
instead of return sum
I think there's a mix-up of terminology going on in that statement. I agree that you should be "passing" some sort of index (or indexed value), but the "return" is valid as is written  = )
0
 
LVL 31

Accepted Solution

by:
farzanj earned 250 total points
ID: 37763005
You don't need sum parameter and termination should be 0.

Function should only be
if ( size > 0)
     return arr[size] + sumOfElements(arr, size - 1);
else
   return arr[0];
 
So, if the array has 3 elements, you should call it with size 2 initially.  There are sure other ways to do the same thing.
0
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 37763032
Aw farzanj...  I know you know better than this  ; )

return arr[size] ...

*grin*
0
 

Author Comment

by:Dmon443
ID: 37763160
Isn't return arr[size] and return arr[0] the same thing? Gives the same results when I try both and logically they are the same thing.

ok so now I have the function as follows:
int sumOfElements(const int arr[], int size)
{  
    if (size > 0)
        return arr[size]+ sumOfElements(arr, size - 1);
    else    
        return arr[0];
               
}
But now this is producing some weird results if I choose 3 numbers to add no matter what numbers I put in the answer is always 4199524 and if I choose 4 numbers same thing happens give a massive number like 4469876. But if I choose 5 numbers to add it works perfectly.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 31

Expert Comment

by:farzanj
ID: 37763310
Kaufmed, I always try to learn from you.  Here is the complete code that I wanted to say.  It works for me and it is recursive.  Kindly tell me how would you write it.  It produces the correct result in every situation.
#include<iostream>

using namespace std;
int sumOfElements(const int[], int);


int main()
{
	int arr[3] = {3, 5, 7};
	int sum = sumOfElements(arr, 2);
	cout << "Sum : " << sum << endl;

	//system("pause");
	return 0;
}

int sumOfElements(const int arr[], int index)
{
	if(index > 0)
	{
		return arr[index] + sumOfElements( arr, index -1);
	}
	else
	{
		return arr[0];
	}
}

Open in new window

0
 
LVL 75

Assisted Solution

by:käµfm³d 👽
käµfm³d   👽 earned 250 total points
ID: 37763313
arr[size] should never be used because arrays are indexed starting at 0, and the maximum index of an array will be 1 less than its size. arr[size] would give you then next slot of memory after the last slot in the array, but since you haven't explicitly requested that slot (and set its value), there is no telling what is in that slot.
0
 
LVL 31

Expert Comment

by:farzanj
ID: 37763320
Hi Kaufmed, I always try to learn from you.  This is my idea and it works fine.  I think my concept is pretty clear as well.  What would you suggest?

#include<iostream>

using namespace std;
int sumOfElements(const int[], int);


int main()
{
	int arr[3] = {3, 5, 7};
	int sum = sumOfElements(arr, 2);
	cout << "Sum : " << sum << endl;
	//system("pause");
	return 0;
}

int sumOfElements(const int arr[], int index)
{
	if(index > 0)
	{
		return arr[index] + sumOfElements( arr, index -1);
	}
	else
	{
		return arr[0];
	}
}

Open in new window

0
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 37763321
@ farzanj
Kindly tell me how would you write it.  It produces the correct result in every situation.
Ah, but in your newest code you are using index rather than size. That is expected. I explained the use of size above (for Dmon443's benefit)  = )
0
 
LVL 31

Expert Comment

by:farzanj
ID: 37763334
I was just using the size term as he was using it.  I always meant index.  I never meant size, sorry for the confusion.  You can see in my first response too as I said.

He has to pass the maximum index of array and it would reduce to 0 eventually.  But in the terminal case, I do not want another recursive call to the function that it why I used return arr[0] alone. Makes sense?
0
 
LVL 31

Expert Comment

by:farzanj
ID: 37763345
Here is a slight variation in my main function:
int main()
{
	int arr[] = {3, 5, 7};
	int max_index = sizeof(arr)/sizeof(int) -1 ;
	int sum = sumOfElements(arr, max_index);
	cout << "Sum : " << sum << endl;
	system("pause");
	return 0;
}

Open in new window


This way you can change the array arr without changing anything else.
0
 

Author Closing Comment

by:Dmon443
ID: 37763362
Thanks guys, it's working perfectly now, learn't something new with index being one smaller than the size of the array.
0
 
LVL 31

Expert Comment

by:farzanj
ID: 37763367
Kaufmed,  any better solution would be highly appreciated :)
0
 
LVL 75

Expert Comment

by:käµfm³d 👽
ID: 37763596
@farzanj

I have no issue with the logic you posted. I was just confused by the terminology. If there's better logic out there, I don't know what it is  = )
0
 
LVL 31

Expert Comment

by:farzanj
ID: 37763600
Thanks Kaufmed, appreciated.
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
C++ Language error 28 193
base64 decode encode 12 119
Modify a small python script 19 96
object oriented programming comparison 5 54
I know it’s not a new topic to discuss and it has lots of online contents already available over the net. But Then I thought it would be useful to this site’s visitors and can have online repository on vim most commonly used commands. This post h…
Does the idea of dealing with bits scare or confuse you? Does it seem like a waste of time in an age where we all have terabytes of storage? If so, you're missing out on one of the core tools in every professional programmer's toolbox. Learn how to …
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

910 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

24 Experts available now in Live!

Get 1:1 Help Now