Question

Write a function that checks if a number is in the Fibonacci sequence using recursion. In C++.

Answer 1

#include <iostream>

using namespace std;

bool is_in_fibonacci_sequence(int n, int f0 = 0, int f1 = 1) {
    if (n < f0) {
        return false;
    } else if (n == f0) {
        return true;
    } else {
        return is_in_fibonacci_sequence(n, f1, f0 + f1);
    }
}

int main() {
    int n;
    cout << "Enter a positive integer: ";
    cin >> n;

    if (is_in_fibonacci_sequence(n)) {
        cout << n << " is in the fibonacci sequence" << endl;
    } else {
        cout << n << " is not in the fibonacci sequence" << endl;
    }
    return 0;
}