Francesco Clemente Francesco Clemente - 1 month ago 33
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

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.