Napisałem ten kod w Pythonie i zastanawiałem się, czy czasami po prostu się nie kończy (zakładając, że mamy nieskończoną pamięć / czas i nie ma ograniczenia głębokości rekurencji).
Intuicyjnie myślisz, że kończy się, ponieważ w pewnym momencie musisz mieć szczęście , a jeśli się nie skończy, masz nieskończoną ilość czasu na szczęście. Z drugiej strony, wraz ze wzrostem głębokości rekurencji, musisz mieć wykładniczo więcej szczęścia.
import random
def random_tree():
if random.random() < 0.5:
return 0
return [random_tree() for _ in range(random.randint(1, 5))]
Jeśli random_tree
nie zawsze się kończy, dlaczego i jaka jest szansa, że się zakończy?
def random_tree(a, b):
if random.random() < a:
return 0
return [random_tree(a, b) for _ in range(random.randint(1, b))]
Lub w pseudokodzie:
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 calls
random_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
random_tree(0.5, 5)
.Odpowiedzi:
źródło