Francesco Clemente -4 years ago 176
C Question

# C: Hofstadter Q sequence with recursion

I've to write a C function that print on screen the first N elements of Hofstadter Q sequence by using recursion.

Hofstadter Q sequence definition is:

Q(1)=Q(2)=2

Q(n)= Q(n-Q(n-1)) + Q(n-Q(n-2))

My code should be ok, but I don't know where to put the printf to print the results.

First numbers are: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, 12, 12, 12, 16, 14, 14, 16, 16, 16, 16, 20, 17, 17, 20, 21, 19, 20, 22, 21, 22, 23, 23, 24, 24, 24, 24, 24, 32, 24, 25, 30, 28, 26, 30, 30 etc.

My code is actually:

``````#include <stdio.h>
int hof(int n);

int main()
{
int n;
int flag;

printf("How many elements to print: ");
scanf("%d",&n);

flag=hof(n);

return 0;
}

int hof(int n) {
int res;

if (n < 3) res = 1;
else res=hof(n-(hof(n-1)))+hof(n-(hof(n-2)));

return res;
}
``````

Thank you.

Answer Source

Your code repeatedly calculates same set of sub-sequences. That means it's both inefficient and there's no single place in your code where you can "insert" the printf.

Using memoization, it can be done as:

``````#include <stdio.h>
int arr[512];

int hof(int n);
int main(void) {

int n;
int flag;

printf("How many elements to print: ");
scanf("%d",&n);

flag=hof(n);

for(size_t i = 1; arr[i]; i++)
printf("%d ", arr[i]);

return 0;
}

int hof(int n){
int res;

if (arr[n]) return arr[n];

if (n < 3) res = 1;
else res=hof(n-(hof(n-1)))+hof(n-(hof(n-2)));

arr[n] = res;
return res;
}
``````

You can change the array size as per your needs or use `malloc()` to dynamically allocate.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download
Latest added