python) Memoization

dictionary = {1 : 1, 2 : 1}

def fibonacci(n):
    if n in dictionary:
        return dictionary[n]
    else:
        output = fibonacci(n-1) + fibonacci(n-2)
        dictionary[n] = output

        return output
number = int(input())
print("fibonacci({}) : {} ".format(number , fibonacci(number)))

### Code Breakdown

- **`dictionary = {1: 1, 2: 1}`**: Initializes a dictionary with the first two Fibonacci numbers. The keys are the position in the Fibonacci sequence, and the values are the Fibonacci numbers themselves. This dictionary serves as a cache to store computed Fibonacci numbers, a technique known as memoization.

- **`def fibonacci(n):`**: Defines the `fibonacci` function that calculates the `n`th Fibonacci number.
  - If `n` is found in the `dictionary`, the function immediately returns the value associated with `n`, avoiding redundant calculations.
  - If `n` is not in the `dictionary`, the function calculates the `n`th Fibonacci number by recursively calling itself to find the (`n-1`)th and (`n-2`)th Fibonacci numbers, adds those two numbers to get the `n`th number, stores this result in the dictionary, and then returns the result. This way, every new Fibonacci number calculated is added to the dictionary, significantly speeding up future calculations for the same `n`.

- **`number = int(input())`**: Takes an integer input from the user and stores it in the variable `number`. This is the position in the Fibonacci sequence for which the user wants to compute the Fibonacci number.

- **`print("fibonacci({}) : {} ".format(number, fibonacci(number)))`**: Prints the `n`th Fibonacci number by calling the `fibonacci` function with `number` as the argument.

### Memoization

The key concept demonstrated here is **memoization**, which is a specific form of caching. Memoization stores the results of expensive function calls and returns the cached result when the same inputs occur again. For the Fibonacci sequence, which inherently performs many redundant calculations in its naive recursive implementation, memoization drastically reduces the number of computations needed to find a Fibonacci number, making it much more efficient.

### Note

- The script uses `input()` to receive user input, which means it expects an input to be provided at runtime. When running this code outside of an interactive environment (like a script in a terminal or an IDE), it will pause execution waiting for the user to enter a number.

- Be cautious with the input size. Although memoization makes calculating Fibonacci numbers more efficient, extremely large inputs can still take a considerable amount of time and may reach the recursion depth limit or cause memory issues due to the large size of the dictionary.