def Fibonacci_R(n):
    if n<=0:
        print("Incorrect input")
    # First Fibonacci number is 0
    elif n==1:
        return 0
    # Second Fibonacci number is 1
    elif n==2:
        return 1
    else:
        return Fibonacci_R(n-1)+Fibonacci_R(n-2)

"""
Explanation: "Fibonacci Numbers" is a common problem that can come up in interviews, not simply to test whether someone knows what it is, but assuming you don't know how to solve for it, how would you go about it?
First, to define what a Fibonacci number is: 
"a sequence such that each number is the sum of the two preceding ones, starting from 0 and 1. That is, and for n > 1"
So we get the sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 for the first 10 numbers. 
Because we are programming a solution, there are different ways to go about it. The main methods are: recursion, dynamic programming, and space optimized.
Functions for the nth Fibonacci number
Recursion Method
End of explanation
"""


FibArray = [0,1]
 
def Fibonacci_DP(n):
    if n<=0:
        print("Incorrect input")
    elif n<=len(FibArray):
        return FibArray[n-1]
    else:
        temp_fib = Fibonacci_DP(n-1)+Fibonacci_DP(n-2)
        FibArray.append(temp_fib)
        return temp_fib

"""
Explanation: Dynamic Programming Method
End of explanation
"""


def Fibonacci_SO(n):
    a = 0
    b = 1
    if n <= 0:
        print("Incorrect input")
    elif n == 1:
        return b
    else:
        for i in range(2,n):
            c = a + b
            a = b
            b = c
        return b

"""
Explanation: Space Optimized Method
End of explanation
"""


q=19
r=[Fibonacci_R(q),Fibonacci_DP(q),Fibonacci_SO(q)]
print(r)

"""
Explanation: The Test
Let's test these
End of explanation
"""


import math 
  
# returns true if x is perfect square, else false
def isPerfectSquare(x): 
    s = int(math.sqrt(x)) 
    return s*s == x 

def is_PS(n): 
    # n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both 
    # is a perferct square 
    return isPerfectSquare(5*n*n + 4) or isPerfectSquare(5*n*n - 4) 

def isFibonacci(n):
    if (is_PS(n) == True): 
        print(n,"is a Fibonacci Number")
    else: 
        print(n,"is a not Fibonacci Number")

isFibonacci(r[0])

"""
Explanation: Better Test
We've proven these provide the output we desire, but is there another way to test whether our result is a Fibonacci Number?
By definition, "A number is Fibonacci if and only if one or both of (5n^2 + 4) or (5n^2 – 4) is a perfect square"
First, let's define our perfect square function, then run it against our output.
End of explanation
"""


[isFibonacci(r[0]),isFibonacci(r[1]),isFibonacci(r[2])]

"""
Explanation: The Test
Let's test these
End of explanation
"""


def Fibonacci_R(n):
    if n<=0:
        print("Incorrect input")
    # First Fibonacci number is 0
    elif n==1:
        return 0
    # Second Fibonacci number is 1
    elif n==2:
        return 1
    else:
        return Fibonacci_R(n-1)+Fibonacci_R(n-2)
txt = int(input("To find the nth Fibonacci Number, type in an integer for that position: "))
print("Your integer",txt,"references the Fibonacci Number",Fibonacci_R(txt))

"""
Explanation: Finally, what if you want to use user input for this? Say you are on a virtual call and they want to run the program themselves and only enter a number, and have it provide the result, as well as confirmations that the result it truly Fibonacci? 
Finding the nth Fibonacci Number
End of explanation
"""


txt = int(input("Please enter an integer to see if it is a Fibonacci Number "))
import math 
def is_PS(n): 
    # n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both 
    # is a perferct square 
    return isPerfectSquare(5*n*n + 4) or isPerfectSquare(5*n*n - 4) 

def isFibonacci(n):
    if (is_PS(n) == True): 
        print("Your integer",txt,"is a Fibonacci Number")
    else: 
        print("Your integer",txt,"is a not Fibonacci Number")
isFibonacci(txt)

"""
Explanation: Is this number a Fibonacci Number?
End of explanation
"""


