Will a recursive sha256 run over all 2^256 inputs before a collision?

Question

Will a recursive sha256 run over all 2^256 inputs before a collision?

Here'a a python program showing my question - will this loop for 2^256 times - given endless memory or will it terminate before - if so when?

import hashlib

# start with 0
input = (0).to_bytes(32, byteorder="little", signed=False)

# dictionary to detect hash collisions - yes, this will eat up ALL memory
hit = {}

print ("first input:" + input.hex())

while (1):
    hash = hashlib.sha256(input).digest()
    
    # do we have a collision?
    assert (hash not in hit), "Collision!"
    
    # store current hash
    hit[hash]=1

    print ("Hash: " + hash.hex())

    # try again with the hash output as input
    input=hash

Answer 1

Short answer: you will "probably" find a collision after 2^128 attempts.

The concept you are looking for is called the birthday problem, explained also very well in this video by Professor Christoph Parr.

One of the approximations from The Birthday Problem is that given a random output space of size n, the probability of an input collision approaches 50% after approximately √n attempts. (2^256)^1/2 = 2^128