Recursive/iterative functions

Question

I'm having a bit of a hard time creating a function, using iteration and recursion to find the sum of all even integers between 1 and the number the user inputs. The program guidelines require a function to solve this three ways:

a formula
iteration
recursion

This is what I have so far:

#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

void formulaEvenSum(int num, int& evenSum)
{
    evenSum = num / 2 * (num / 2 + 1);
    return;
}

void loopEvenSum(int num, int& evenSum2)
{

}


int main()
{
    int num, evenSum, evenSum2;

     cout << "Program to compute sum of even integers from 1 to num.";
     cout << endl << endl;

     cout << "Enter a positive integer (or 0 to exit): ";
     cin >> num;

     formulaEvenSum(num, evenSum);
     loopEvenSum(num, evenSum2);

     cout << "Formula result = " << evenSum << endl;
     cout << "Iterative result = " << evenSum2 << endl;

     system("PAUSE");
     return 0;

}

So what's the problem? You forgot to add that crucial bit of information — Ed Swangren
– Ed Swangren, Commented Oct 14, 2012 at 17:47

Raunak Mukhia · Accepted Answer · 2012-10-14 18:04:10Z

3

Using iteration to find the sum of even number is as given below.

void loopEvenSum(int num, int &evenSum2)
{
    evenSum2=0;
    for (i=2;i<=num;i++)
    {
        if(i%2==0)
            evenSum2+=i;
    }
}

The following code though not the most efficient can give you an idea how to write a recursive function.

void recursiveEvenSum(int num,int &evenSum3,int counter)
{
    if(counter==1)
        evenSum3=0;
    if(counter>num)
        return;
    if(counter%2==0)
        evenSum3+=counter;
    recursiveEvenSum(num,evenSum3,counter+1);
}

Now you can call recursiveEvenSum(...) as

int evenSum3;
recursiveEvenSum(num,evenSum3,1);

answered Oct 14, 2012 at 18:04

Raunak Mukhia

3881 silver badge11 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Richard · Accepted Answer · 2012-10-14 17:47:46Z

You should be able to build an iterative solution using a for loop without too much problem.

A recursive solution might take the form:

f(a)
  if(a>0)
    return a+f(a-1)
  else
    return 0

f(user_input)

You have to differentiate between a case where you "dive deeper" and one wherein you provide an answer which doesn't affect the total, but begins the climb out of the recursion (though there are other ways to end it).

An alternative solution is a form:

f(a,sum,total)
  if(a<=total)
    return f(a+1,sum+a,total)
  else
    return sum

f(0,0,user_input)

The advantage of this second method is that some languages are able to recognise and optimize for what's known as "tail recursion". You'll see in the first recursive form that it's necessary to store an intermediate result for each level of recursion, but this is not necessary in the second form as all the information needed to return the final answer is passed along each time.

Hope this helps!

yohannist · Accepted Answer · 2012-10-14 17:51:16Z

0

I think this does it Don't forget to initialize the value of evenSum1, evenSum2 and evenSum3 to 0 before calling the functions

void loopEvenSum(int num, int& evenSum2)
{
    for(int i = num; i > 1; i--)
        if(i%2 == 0)
            evenSum2+=i;
}

void RecursiveEvenSum(int num, int & evenSum3)
{
    if(num == 2)
    {
        evenSum3 + num;
        return;
    }
    else
    {
        if(num%2 == 0)
            evenSum3+=num;
        num--;
        RecursiveEvenSum(num, evenSum3);
    }
}

answered Oct 14, 2012 at 17:51

yohannist

4,2143 gold badges38 silver badges59 bronze badges

Comments

taufique · Accepted Answer · 2012-10-14 18:09:42Z

0

void loopEvenSum(int num, int& evenSum2)
{
    eventSum2 = 0;
    for(int i = 1 ; i <= num; i++){
        (i%2 == 0) eventSum += i;
    }
}


void recurEvenSum(int num, int& evenSum3)
{
    if(num == 1) return;
    else if(num % 2 == 0) {
        eventSum3 += num;
        recurEvenSum(num-1, eventSum3);    
    }
    else recurEvenSum(num-1, eventSum3); 

}

btw, you have to initialize evenSum to 0 before calling methods.

edited Oct 14, 2012 at 18:09

answered Oct 14, 2012 at 17:53

taufique

2,7891 gold badge32 silver badges40 bronze badges

1 Comment

Michael Rea Over a year ago

For the recursive function, it should have the same output as the other two functions. For example, if the user inputs 10, all three should output 30.

nemesis · Accepted Answer · 2012-10-14 18:47:20Z

0

the recursive method can be much simpler if you return int instead of void

void iterEvenSum(int num, int& evenSum2)
{
    evenSum2 = 0;
    if (num < 2) return;
    for (int i = 0; i <= num; i+=2)
    evenSum2 += i;
}

int recurEvenSum(int num)
{
    if (num < 0)    return 0;
    if (num < 4)    return 2;
    return num - num%2 + recurEvenSum(num-2);
}

edited Oct 14, 2012 at 18:47

answered Oct 14, 2012 at 17:55

nemesis

2631 gold badge4 silver badges11 bronze badges

Comments

grobx · Accepted Answer · 2016-01-25 20:49:53Z

To get the sum of all numbers divisible by two in the set [1,num] by using an iterative approach, you can loop through all numbers in that range, starting from num until you reach 2, and add the number of the current iteration to the total sum, if this is divisible by two.

Please note that you have to assign zero to evenSum2 before starting the loop, otherwise the result will not be the same of formulaEvenSum().

void loopEvenSum(int num, int& evenSum2)
{
    assert(num > 0);
    evenSum2 = 0;
    for (int i=num; i>=2; --i) {
        if (0 == (i % 2)) {
            evenSum2 += i;
        }
    }
}

To get the same result by using a recursive approach, instead of passing by reference the variable that will hold the sum, i suggest you to return the sum at each call; otherwise you'll need to hold a counter of the current recursion or, even worse, you'll need to set the sum to zero in the caller before starting the recursion.

int recursiveEventSum(int num)
{
    assert(num > 0);
    if (num == 1) {
        return 0;
    } else {
        return ((num % 2) ? 0 : num) + recursiveEventSum(num-1);
    }
}

Please note that, since you get an even number only if you subtract two (not one) from an even number, you could do optimisation by iterating only on those numbers, plus eventually, the first iteration if num was odd.

Collectives™ on Stack Overflow

Recursive/iterative functions

6 Answers 6

Comments

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related