Özyineleme
Özyineleme (recursion), bir fonksiyonun tanımında yine fonksiyonun kendisinin kullanıldığı fonksiyondur.

Özyineleme fonksiyonu örnekleri için tıklayınız.

Amaç
Özyineleme, problemi daha ufak parçalara ayırmaya yarar. Böylece problemin daha basit bir versiyonu çözülerek bütünün çözümüne adım adım ilerlenir. Yinelenen her adımda problemin boyutu da küçülür.

Örnek
Örneğin n'ye kadar olan tam sayıların toplamı, n-1'e kadar olan tam sayıların toplamını bulmayı da içerir. Benzer şekilde n-2'e kadar olan tam sayıların toplamını bulmayı da içerir. Bu işlem böylece 1'e kadar gider. Bu durumda problem şu hale dönüşür:
 

topla(n) = n + topla(n-1)

Yukarıdaki şekilde verilen tanımlamaya özyinelemeli (recursive definition) denir.

Üç bölüm
Özyineleme fonksiyonu şu üç bölümden oluşur:

• Sonsuz döngüye (infinite recursion, stack overflow) girmemek için ne zaman durulacağını bildiren koşul (base case, base condition). Bu koşul özyineleme gerektirmez.
• Problemin daha basite indirgendiği kısım. (reduction)
• Fonksiyonun kendini çağırdığı kısım.

Avantaj
Aynı problem döngü ile çözülebilmesine rağmen, özyineleme yaklaşımı daha temiz ve kolay bir ifadeye sahiptir.

Dezavantaj
Bütün özyineleme fonksiyonları, koşum boyunca son koşula varana dek yığın bellekte (stack) tutulması gerektiği için iteratif (döngüsel) yönteme kıyasla çok daha fazla bellek alanına ihtiyaç duyar.

Örnek
1'den verilen bir tam sayıya kadar olan bütün tam sayıların toplamını veren algoritma nedir?
 

function recursiveSum(n) { if(n == 1) return 1; return n + recursiveSum(n-1); }

 
Bahsi geçen özyinelemeli çözüme göre fonksiyonların çağrılma hiyerarşisi şöyle olur:
 

recursiveSum(5);       recursiveSum(4);          recursiveSum(3);             recursiveSum(2);                recursiveSum(1);                return 1;             return 2 + 1;          return 3 + 2 + 1;       return 4 + 3 + 2 + 1;    return 5 + 4 + 3 + 2 + 1;