Recursion (Tower of Hanoi)
~~~~~~~~~~~~~~~~~~~~~~~~~~

- Solving a problem by reducing it to solving one (or several) sub-problems (of smaller size)
- requires a base case with known solution:

i.e. with Hanoi
Base Case: for one disk: move from source to dest
For more than 1 (n disks):
a) Move n-1 disks from source to spare (this is recursive part)
b) Move the 1st (largest) disk from source to dest
c) Move the other n-1 disks from spare to dest (this is recursive also)

How many moves does it take?
This is exponential growth, takes 2^n-1 move at best

Legend of Hanoi:
64 gold disks, 3 diamond posts
When moves are finished, the world will end

2^64 - 1 = 584,942,417,355 *years*, assuming 1 move per second
For reference, Age of universe 13-14 billion years.

von Neumann architecture:
~~~~~~~~~~~~~~~~~~~~~~~~~

Algorithm -> (programming) -> program in high-level language -> (compilation) -> program is assembly language -> program in machine code -> execution

Architecture:
1. Arithmetic-Logic Unit (ALU) - does the actual operation, mathematical (+/-/*) and logical (and/not/or/xor).
2. Control Unit (controls the activity of the rest of the device)
3. Memory (stores instructions and data)
4. Input/Output (I/O)
~5. BUS - Data Path connecting the parts

Instruction cycle:
-Fetch
-Decode
-Evaluate
-Fetch Operands
-Execute
-Store Results

Most computers are not purely following this structure, can check for interrupts, etc.

von Neumann bottleneck: moving a lot of information to/from memory, everything else has to wait.
Possible solution, separate datapath, make one for instructions, one for data.


Machine Language Instructions:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

STV A B (store value; A - value, B - location)
PRT A (print value; A - location)
CLA (clear accumulator)
ADD A (add to accumulator, A - location)
SUB A (subtract from accumulator, A - location)
ST A (store accumulator value, A - location)
HLT (halt)
BUN A (uncondition branch, A - line to go to)
RD A (store input, A - location)
BRI R#, R#', A (branch or increment, branch is R# >= R#', else increment R#, A - line to go to)
PRT R1, A (print element of A array at index specified by value in R1)
SETR #A, R# (store value A in R#)
SETR A, R# (store value at location A in R#)
BGE A (branch if value in accumulator >= 0, A - line to go to)
BGT A (bracch if value in accumulator > 0, A - line to go to)
BLE A (branch if value in accumulator <= 0, A - line to go to)
BLT A (branch if value in accumulator < 0, A - line to go to)



Example with index register:

Program to print A(1), A(2), .... A(10)
(assuming A(1), A(2).....A(10) have been defined, i.e. array A has been
defined)

int i = 0
while (i <= 10) {
  i = i+1
  print A(i)
}

SETR 0, R1 (start)
SETR 10, R2
BRI R1, R2, endl (branch if C[R1] >= C[R2], else increment register by
1)
PRT R1, A
BUN start
 (endl)