Question

Please follow the instructions and solve it by C++. Thank you!

What to Submit

Submit the following:

1) Your .cpp file of the solution.

2) For what n value (approximately) does your computer stop producing output? Why is this? Enter your answer in the 'Comments' field when you submit the file.  

So far in our study of recursion we identified a few common recursive number sequences, such as the Fibonacci numbers. Number sequences like this are not recursive algorithms themselves -- their definitions are ways of generating the "nth term", rather than ways of breaking down a larger problem -- but they can serve as good examples of the practical limits of recursion.

Some sequences are notoriously hard to compute (with recursion, at least) because of the deep layers required, as we will see in this week's lab.

Golomb's sequence is known as "self describing" -- it seems to define itself. It is defined as the sequence of natural numbers such that n appears exactly G(n) times in the sequence. Here are the first few values of G(n) for some n:

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
G(n)	1	2	2	3	3	4	4	4	5	5	5	6	6	6	6

The sequence starts at 1, with G(1) = 1.

It's not too hard if you step through it one term at a time.

For n = 1, G(n) is 1. If you look at the sequence (the entire sequence G(n) all the way to infinity -- it seems to "know" about itself), 1 appears only 1 time.

For n = 2, G(n) is 2. Looking again at the G(n) sequence, the number 2 appears 2 times.

For n = 3, G(n) is 2. You can see that 3 appears 2 times.

For n = 4, G(n) is 3. ... and 4 appears 3 times.

And so on and so forth.  

Assignment

Write a C++ program that recursively computes each term of G(n) up to and including a given n. You can "hard code" the input value (the program does not need to accept any input) but you will need to set it sufficiently high so you can determine your answer for the second part below -- you may need to experiment with different values.

The formula is:

G(n) = 1 + G(n - G(G(n - 1)))

Remember to think about the base case.

Example Output

The output of your program does not need to exactly match this, but please make sure each term is output on a separate line along with the n for that term.

For n = 15:

1: 1
2: 2
3: 2
4: 3
5: 3
6: 4
7: 4
8: 4
9: 5
10: 5
11: 5
12: 6
13: 6
14: 6
15: 6

Answer 1

using a recursive solution, the formula gives result upto 89.
This is because as the recursion goes deeper, the compiler has to store an activation record for every recursion call and at a stage, the memory of the activation gets eaten up. This causes segmentation error and the program crashes.
However, this can be improved by using arrays instead of recursion. This is called as memoisation. What we do here is store a few values for the initial numbers and instead of function calls, we refer the number in the array. This solves the problem associated with recursion, but this also has a problem with the memory. An array cannot hold more than 10^7 elements. Therefore the highest possible number for which the value can be retrieved is 222222.

Code:

Using Recursion:

#include<iostream>
using namespace std;
unsigned long long solve (unsigned long long int n)
{
   if(n == 1) return 1;
   if(n == 2 || n == 3) return 2;
   return (1 + solve( n - solve( solve( n - 1 ) ) ) );
}
int main()
{
   cout<<"Enter n"<<endl;
   unsigned long long i, n;cin >> n;
   for(i = 1 ; i <= n ; i++)
   {
       cout << i << ": " << solve(i) << endl;
   }
   return 0;
}

Using Arrays:

#include<iostream>
using namespace std;
unsigned long long solve (unsigned long long int n)
{
   if(n == 1) return 1;
   if(n == 2 || n == 3) return 2;
   return (1 + solve( n - solve( solve( n - 1 ) ) ) );
}
int main()
{
   unsigned long long a[222223], i, n;a[1] = 1;a[2] = 2;a[3] = 2;
   cout<<"Enter n"<<endl;cin>>n;
   for(i = 1 ; i <= n ; i++)
   {
      
       a[i] = 1 + a[i - a[a[i - 1]]];
   }
   for(i = 4 ; i <= n ; i++)
   {
       cout << i << ": " << a[i] << endl;
   }
   return 0;
}

Output:

Using recursion:

Using Arrays: