Dallanan çağrılar: al ya da alma

Bazı problemlerde her adımda bir seçim vardır: bu elemanı al ya da alma, buraya açan parantez koy ya da kapatan. Özyineleme iki seçeneği de dener: her biri için kendini bir kez çağırır. Çağrılar artık bir zincir değil, bir ağaçtır.

1def count(values, i, left):
2    if left == 0:
3        return 1
4    if i == len(values) or left < 0:
5        return 0
6    take = count(values, i + 1, left - values[i])
7    skip = count(values, i + 1, left)
8    return take + skip

Bedeli büyüktür: her eleman çağrı sayısını ikiye katlar. 20 eleman bir milyon, 30 eleman bir milyar çağrıdır. Bu yüzden dallanan özyinelemede iki soru önemlidir: bir dalı erken kesebilir miyim (hedef eksiye düştüyse devam etme), ve aynı alt problemi tekrar tekrar mı çözüyorum? İkincisinin cevabı Dinamik Programlama konusudur.