Tag Archive : Mutual Recursion with example of Hofstadter

Hofstadter Q-Sequence in Python

In this article, we have built a program to find the value of a number in the Q-Sequence (By Using Hofstadter Q-Sequence) with the Python code. Please install python 3.8 from the link given below to run this code.

I prefer you to use atom text editor to type your code or to save the given code:

You can download the the Hofstadter Q-Sequence.py from GitHub using the given link:

Link for the code in GitHub

Example Input:





def Q(n):
        if n>0 and n<3:
           return 1
        elif n<0:
           return 'Invalid'
           return Q ( n - Q ( n - 1 ) ) + Q ( n - Q ( n - 2 ) )
    except:return "Enter an INTEGER value!"

Code Explanation:

In this code, we get an input from the user which is the value of n in Q(n) .

Q ( 1 ) = Q ( 2 ) = 1 , Q ( n ) = Q ( n − Q ( n − 1 ) ) + Q ( n − Q ( n − 2 ) ) , n > 2

Hofstadter Q sequence Definition

Function Definition:

Here, we define a function that takes n as its parameter (input).
We use ‘try and ‘except’ in order to prevent unnecessary errors .

The error is caused only if the user enters anything other than float or int.

Here, we use Recursion in order to call back the same function to use Q ( n − Q ( n − 1 ) ) + Q ( n − Q ( n − 2 ) ) .

If the user enters a negative integer, the code outputs “Enter an INTEGER value!”

The base of the recursion is the condition “if n>0 and n<3:”
It returns 1 if the value becomes <3 (0,1 or 2).

Function Call:

At last, we call the function Q with int(input()) as parameter and print it out


The above article explains the Hofstadter Q-Sequence using python coding. If you want to download the code from GitHub, click here. If you have any questions or feedback on this, feel free to post in the comments section below.