Рекурсия

от Уикипедия, свободната енциклопедия

В математиката и информатиката рекурсията е начин да се определи нещо (обикновено математически обект или част от компютърна програма) чрез обръщане към себе си.

Най-често срещаният пример за рекурсивно дефинирана функция е следната дефиниция за функцията f(n), която е факториел;

f(0) = 1
f(n) = n · f(n − 1)   за всяко естествено число n > 0

С тази дефиниция може да се изчисли f(3) например:

f(3) = 3 · f(3 − 1)

     = 3 · f(2)
     = 3 · 2 · f(2 − 1)
     = 3 · 2 · f(1) 
     = 3 · 2 · 1 · f(1 − 1)
     = 3 · 2 · 1 · f(0)
     = 3 · 2 · 1 · 1
     = 6