# File:    traceFib.py
# Author:  Dr. Gibson
# Date:    11/10/2017
# Section: N/A
# E-mail:  k.gibson@umbc.edu
# Description:
#   This file contains python code that recursively
#   finds the Xth Fibonacci number, but also 'shows'
#   how deep each call is on the Python stack 

CHAR = "--"

##############################################################################
# fib()   calculates the Xth Fibonacci number
# Input:  pos;    an int, the position of the desired Fibonacci number
#         indent; a string, a series of "--" showing the 'depth' on the stack
# Output: returns the final answer, or the string
#                 "that's not valid" for invalid queries
def fib(pos, indent):
    print(indent + "Getting position #" + str(pos))

    newIndent = indent + CHAR  # create a new, deeper indent for user

    # BASE CASES:
    if pos <= 0:  #"bad case"
        return "not valid"
    elif pos == 1:  # first Fib number
        return 0
    elif pos == 2:  #second Fib number
        return 1
    # RECURSIVE CASE:
    else:
        # RECURSIVE CALL:
        return fib(pos - 1, newIndent) + fib(pos - 2, newIndent)

#########################################################################
# ordinal() returns the correct 'end' for a number (1st, 2nd, 3rd, etc.)
# Input:    num; an integer to find the end for
# Output:   end; a string of the correct end for that number
def ordinal(num):
    if num % 100 == 11 or num % 100 == 12 or num % 100 == 13:
        return "th"   # 'rule breaking' numbers; 112th, etc.
    elif num % 10 == 1:
        return "st"   # 1st, 21st, etc.
    elif num % 10 == 2:
        return "nd"   # 2nd, 42nd, etc.
    elif num % 10 == 3:
        return "rd"   # 3rd, 103rd, etc.
    else:
        return "th"   # all other numbers; 78th, 930th, etc.
        

    

    
    
def main():
    pos = int(input("What Xth Fibonacci number do you want to know? "))
    ans = fib(pos, "")
    print("The", pos, "th Fibonacci number is", ans)

main()