מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/חשיבה רקורסיבית/דג הסלמון/הרקורסיה הפשוטה

נגדיר כ$m(k)$ את הזמן המינימלי הנדרש לנוח בברכה $1$, לשחות מברכה $1$ לברכה $k$, ולנוח בברכה $k$.

תבנית:משפט

תבנית:הוכחה

הבעיה היחידה היא שאיננו יודעים את $i$, אבל קל לבדוק מהו ה$i$ המשתלם ביותר בעזרת לולאה:

# Calculates the minimum time for the fish to swim up to (including) some pool (k).
# Takes the up-to pool number (k).
Min-Time(k)
1	if k == 1
2		return Resting-Times[k]
		
3	min-time = ∞
	
4	for i in [1, ..., k - 1]
5		guess = Min-Time(i) + 2 * (1.5^(k - i) - 1) + Resting-Times[k]
					
6		if guess < min-time
7			min-time = guess
			
8	return min-time

תבנית:הארה