c++: Exercises – Recursion

Exercise 1:

Write a recursive method called sum with the following header:

int sum(int low, int high) which takes two parameters, low and high, and returns the sum of the integers between low and high inclusive. For example, the method calls below:

Cout<< sum(4, 4);

Cout<< sum(1, 3) ;

Cout<< sum(6, 9);

Cout<< sum(20, 100) ;

should produce the following output:

4

6

30

4860

 

#include <iostream>
using namespace std;

int sum(int low,int high)
{
  if(low > high)
    return 0;
  return (low + sum(low+1,high));
}
int main()
{
  cout << sum(4,4) << endl;
  cout << sum(1,3) << endl;
  cout << sum(6,9) << endl;
  cout << sum(20,100) << endl;
  return 0;
}

 

Exercise 2:

Consider the following sequence of numbers:  0, 1, 2, 3, 6, 11, 20, 37, 68, 125, 230, 423, 778, 1431, 2632, ….

The sequence starts 0, 1, 2 and from then on each number is the sum of the previous 3 numbers. Write a recursive method called sequence, which is passed a parameter n, of type int, and returns the value at position n in this sequence.

For example:

sequence(0) should return 0,

sequence(1) should return 1,

sequence(2) should return 2,

sequence(3) should return 3,

sequence(4) should return 6,

sequence(5) should return 11, etc

#include <iostream>
using namespace std;
int sequence(int n)
{
  if(n < 3)
    return n;
  return (sequence(n-1) + sequence(n-2) + sequence(n-3));
}
int main()
{
  cout << sequence(0) << endl;
  cout << sequence(1) << endl;
  cout << sequence(2) << endl;
  cout << sequence(3) << endl;
  cout << sequence(4) << endl;
  cout << sequence(5) << endl;
  return 0;
}

 

Exercise 3:

Give the output of the following program.

 

#include <iostream>
using namespace std;

int f(int n)
{
  if(n%2 == 0)
    return (n/2);
  return f(3*n + 1);
}
int main()
{
  cout << f(5) << endl;
  cout << f(7) << endl;
  cout << f(8) << endl;
  return 0;
}

 

Exercise 4: Give the output of the following program.

int TheValue(int A, int B, int N)

{

int ReturnValue;

cout << “Enter: A = ” << A << ” B = ” << B << endl;

int C = (A + B) / 2;

if (C * C <= N)

ReturnValue = C;

else

ReturnValue = TheValue(A, B-1, N);

cout << “Leave: A = ” << A << ” B = ” << B << endl;

return ReturnValue;

}

 

#include <iostream>
using namespace std;

int TheValue(int A, int B, int N)
{
int ReturnValue;
cout << "Enter: A = " << A << " B = " << B << endl;
int C = (A + B) / 2;
if (C * C <= N)
  ReturnValue = C;
else
  ReturnValue = TheValue(A, B-1, N);
cout << "Leave: A = " << A << " B = " << B << endl;
return ReturnValue;
}

int main()
{
  TheValue(1,2,1);
  return 0;
}

 

Exercise 5: 

Write a recursive function that calculates and returns the sum of elements with even index in an array of integers.

 

#include <iostream>
using namespace std;

int sumEven(int a[],int size)
{
  if(size <= 0)
    return 0;
  if((size-1) %2 ==0)
    return (a[size-1] + sumEven(a,size-1));
  else
    return sumEven(a,size-1);
}
int main()
{
  int a[5] = {1,2,3,4,5};
  cout << sumEven(a,5) << endl;
  return 0;
}

 

Exercise 6:

Write a recursive function commons that returns the number of common values in two given arrays of integers.

 

#include <iostream>
using namespace std;

int commons(int a1[],int a2[],int size1,int size2)
{
  int flag = 0;

  if(size2 == 0)
    return 0;
  for(int i=0;i<size1;i++)
    if(a1[i] == a2[size2-1])
    {
      flag =1;
      break;
    }
    return (flag + commons(a1,a2,size1,size2-1));
}

int main()
{
  int a1[4] = {1,3,5,6};
  int a2[9] = {1,2,3,4,7,8,9,5};

  cout << commons(a1,a2,4,9) << endl;
  return 0;
}