Find The Pell Number Using C++

In terms of numbers, the Fibonacci sequence and the Pell numbers sequence have a similar recurrence relation. The Pell numbers are defined by the recurrence relation.

p(n)=2*p(n-1)+p(n-2)

With their initial values are p(0)=0 & p(1)=1 .

These are the first few Pell numbers: 0, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461,... Write a function called int pell(int n) to return P n .

Example:

Input : n = 2
Output :1
Input  : n = 9
Output : 985
Input  : n = 13
Output : 33461

In order to find Pell numbers in C++, we can write a simple algorithm that iterates through the sequence and calculates each Pell number based on the two Pell numbers before it. This algorithm can be implemented in two different ways: recursively or iteratively.

Approach 1: Recursive Approach

Let us take an example to illustrate the pell number in C++ using Recursive Approach.

#include <iostream>

using namespace std;

// Function to calculate the nth Pell number recursively
int calculatePellNumber(int n) {
    // Base cases for n = 0 and n = 1
    if (n <= 1)
        return n;
    
    // Recursive calculation using the Pell number recurrence relation
    return 2 * calculatePellNumber(n - 1) + calculatePellNumber(n - 2);
}

int main() {
    int position; // Position of the Pell number to find
    cout << "Enter the position of the Pell number to find: ";
    cin >> position; // Input position from the user
    
    // Calculate and output the Pell number at the given position
    cout << "The Pell number at position " << position << " is: " << calculatePellNumber(position) << endl;
    
    return 0;
}

Output:

Enter the position of the Pell number to find: 8
The Pell number at position 8 is: 408

Explanation:

In order to use recursion, we calculatePellNumber (n-1) && calculatePellNumber (n-2) until n is equal to or less than 2 because we are aware that the pell numbers up to 2 are the same as the input. O(N) , where N is the specified number, is the overall time complexity of the program mentioned above.

• ✅ The Pell number recurrence relation is used by the function calculatePellNumber to recursively calculate the nth Pell number.
• ✅ In order to find the Pell number's position, the primary function requests input from the user.
• ✅ After passing in the input position, it invokes the calculatePellNumber function and outputs the outcome.

Approach 2: Iterative Approach

Let us take an example to illustrate the pell number in C++ using iterative Approach.

#include <iostream>

using namespace std;

int main() {
    int position = 10; // Given position to find the Pell number.
    int prevPrevPell = 0; // Initial value of P(n-2).
    int prevPell = 1; // Initial value of P(n-1).
    int currentPell; // Placeholder for the current Pell number.

    // If the given position is less than or equal to 2, the Pell number is the same as the position.
    if (position <= 2) {
        cout << "Pell number at position " << position << ": " << position << endl;
    } else {
        // Loop to find Pell number at the given position using iteration.
        for (int i = 2; i <= position; i++) {
            currentPell = 2 * prevPell + prevPrevPell;
            prevPrevPell = prevPell; // Update P(n-2) for the next iteration.
            prevPell = currentPell; // Update P(n-1) for the next iteration.
        }

        cout << "Pell number at position " << position << ": " << currentPell << endl;
    }

    return 0;
}

Output:

Pell number at position 10: 2378

Explanation:

We are traversing from 2 to n in the provided program to update the values for prevprevPell (n-2) to prevPell (n-1) and prevPell n-1 to currentPell until we reach n.

• ✅ The position variable denotes the postion to find the pell number.
• ✅ P(n-2) represents the "PREVPREVPELL" number which is initialized to 0.
• ✅ P(n-1) represents the "PREVPELL" number which is initialized to 1.
• ✅ The loop determines the Pell number by iterating from the second number to the specified position.
• ✅ Using the Pell number recurrence relation, the current Pell number is updated.
• ✅ Lastly, printing of the Pell number at the specified position is done.

Conclusion:

The Nth pell number puzzle was solved by us using recursion and iteration. Additionally, we were taught the C++ program for the problem and our entire Normal and Efficient method of solving it. The same program can be written in a variety of languages, such as C, Java, Python, etc.