Vad är rekursion?

Ett rekursivt problem

Regeln: För att få ett fibonaccital addera de två föregående fibonaccitalen.

Rekursionen består i att gå tillbaka (latin: recurrere) och upprepa regeln.

Pga "två föregående" behövs initialt två startvärden \( \; \mathbf{F_1} \, \) och \( \, \mathbf{F_2} \, \).

Rekursionsformeln kallas i matematiken för differensekvation av andra ordningen

som kan lösas explicit, vilket är komplicerat, se Matte 3c.

Vi föredrar programmering med rekursiv metod:

Fib() är en rekursiv metod därför att den anropar sig själv i sin egen definition (ovan).