teaching.codes

Recursive Functions

Improved Recursive Fibonacci

A dictionary is a data structure that can be used as a key-value pair storage. Instead of providing index values as in tuples, the dictionary elements can be accessed and modified by using non-consecutive or non-integer keys. Dictionaries are defined by using a pair of curly braces and their values can be modified unlike the tuples.

# initialize an empty dictionary of fibonacci numbers
fibonacciDictionary = {}


def fibonacci(number):
    result = 0

    if (number == 0 or number == 1):
        result = number
        if (not number in fibonacciDictionary):
            fibonacciDictionary[number] = result

    elif (not number in fibonacciDictionary):
        # if this number does not exist in the fibonacci dictionary,
        # calculate it and insert into the dictionary
        result = fibonacci(number - 1) + fibonacci(number - 2)
        fibonacciDictionary[number] = result
        print("fibonacci function is being called recursively for numbers: ", number - 1, "and", number - 2)

    else:
        result = fibonacciDictionary[number]
        print("fibonacci value was previously calculated for", number,
              "returning the value", result, "from the dictionary, and NOT calling the function recursively")

    return result


number = 0
print(number, "->", fibonacci(number))
number = 1
print(number, "->", fibonacci(number))
number = 2
print(number, "->", fibonacci(number))
number = 3
print(number, "->", fibonacci(number))
number = 4
print(number, "->", fibonacci(number))
number = 5
print(number, "->", fibonacci(number))
number = 6
print(number, "->", fibonacci(number))
number = 7
print(number, "->", fibonacci(number))
number = 8
print(number, "->", fibonacci(number))
number = 9
print(number, "->", fibonacci(number))
number = 10
print(number, "->", fibonacci(number))


number = 3
print(number, "->", fibonacci(number))
number = 10
print(number, "->", fibonacci(number))
number = 7
print(number, "->", fibonacci(number))

print(fibonacciDictionary)