'''
This code was written in 15-113 lecture.
It is only for demonstrational purposes, and may contain
dubious style and even an occasional bug.
'''

import inspect
import traceback

def fact(n):
    # This version is iterative, so we can compute fact(1000) which
    # we will use to test our recursive versions below
    result = 1
    for k in range(2, n+1):
        result *= k
    return result

fact1000 = fact(1000) # This is a Very Large Number
# print(fact1000)

def tailRecursionWithCodeRewriting(f):
    code = inspect.getsource(f)
    codeLines = code.splitlines()[1:] # skip @tailRecursion
    codeLines.insert(1, '  while True:')
    parameters = list(inspect.signature(f).parameters)
    parmString = ','.join([v.replace("'",'') for v in parameters])
    lastLine = codeLines[-1]
    lastLine = lastLine.replace('return', f'{parmString} = ')
    lastLine = lastLine.replace(f.__name__, '')
    codeLines[-1] = lastLine
    newCode = '\n'.join(codeLines)
    exec(newCode, globals())
    return globals()[f.__name__]

class TailRecursionException(Exception):
    def __init__(self, args):
        self.args = args

def recursingInFn(fnName):
    stack = traceback.extract_stack()
    stackFnNames = list(reversed([ frameSummary.name for frameSummary in stack ]))
    return stackFnNames.count(fnName) > 1

def tailRecursionWithExceptions(f):
    def g(*args):
        while True:
            if recursingInFn(f.__name__):
                raise TailRecursionException(args)
            else:
                try:
                    return f(*args)
                except TailRecursionException as e:
                    args = e.args
    return g

def fact(n):
    # This version does not use tail recursion!
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

def fact(n, tally=1):
    # This version is changed so that it does use tail recursion!
    if n == 0:
        return tally
    else:
        return fact(n-1, n*tally)

try:
    print(fact(1000) == fact1000)
except Exception as e:
    # The tail-recursive version failed with stack overflow as expected
    # since Python does not automatically handle tail recursion.
    print(e)

def fact(n, tally=1):
    # This is what we want our code-rewriting to do:
    while True:
        if n == 0:
            return tally
        else:
            n, tally = (n-1, n*tally)

print(fact(1000) == fact1000) # This works, but only because we manually
                              # edited our code to eliminate tail recursion

@tailRecursionWithCodeRewriting
def fact(n, tally=1):
    # This version is changed so that it does use tail recursion!
    if n == 0:
        return tally
    else:
        return fact(n-1, n*tally)

print(fact(1000) == fact1000) # This works using code rewriting

@tailRecursionWithExceptions
def fact(n, tally=1):
    # This version is changed so that it does use tail recursion!
    if n == 0:
        return tally
    else:
        return fact(n-1, n*tally)

print(fact(1000) == fact1000) # This works using exceptions