I wrote this Python code, and wondered if it sometimes simply doesn't terminate (assuming we had infinite memory/time and no recursion depth limit).Intuitively you'd think it terminates, since at some point you must get lucky, and if it doesn't terminate you have an infinite amount of time to get lucky. On the other hand, as the recursion depth increases you must become exponentially more lucky.import randomdef random_tree():    if random.random() < 0.5:        return 0    return [random_tree() for _ in range(random.randint(1, 5))]If random_tree doesn't always terminate, why, and what is the chance that it does terminate?I've tried to calculate it using $P = 1 - (1 - 0.5)(1 - (P + P^2 + P^3 + P^4 + P^5)/5)$, which in it's terrific uselessness either gives the answer ~$0.684124$ or... $1$. Probably more complicated, but also intriguing to me, what is the termination chance  $P(a, b)$ for:def random_tree(a, b):    if random.random() < a:        return 0    return [random_tree(a, b) for _ in range(random.randint(1, b))]Or in pseudo-code:random_tree(a, b) is a function that either:    - returns 0 with probability a    - returns a list containing the results of 1 to b      (uniformly chosen from this inclusive range) recursive callsrandom_tree(a, b):    if rand() < a # rand() is a random real on [0, 1)        return 0    list = []    len = randint(1, b) # uniform random integer from 1 to b inclusive    do len times        append random_tree(a, b) to list    return list
What is the chance that this code terminates?
trees;probability theory;termination
This is an example of a branching process. The behavior of a branching process depends on the expected number of children, which in your case is $1.25 > 1$. When this number is at most 1, the process gets extinct with probability 1. When the number is more than 1, it has a chance of surviving forever; the extinction probability is just what you calculated — you need to select the root which is smaller than 1.