# 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 = {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 = {1,3,5,6};
int a2 = {1,2,3,4,7,8,9,5};

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