CODEWITHSUNDEEP
c++
Michael Rea
Michael Rea

Reputation: 21

Recursive/iterative functions

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:

  1. a formula
  2. iteration
  3. 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;

}

Upvotes: 2

Views: 6489

Answers (6)

grobx
grobx

Reputation: 343

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.

Upvotes: 0

nemesis
nemesis

Reputation: 263

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);
}

Upvotes: 0

taufique
taufique

Reputation: 2751

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.

Upvotes: 0

Raunak Mukhia
Raunak Mukhia

Reputation: 388

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);

Upvotes: 3

yohannist
yohannist

Reputation: 4204

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);
    }
}

Upvotes: 0

Richard
Richard

Reputation: 61259

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!

Upvotes: 0

Related Questions