Rekürsiyon, bir fonksiyonun veya prosedürün kendisini çağırma sürecidir. Bu, genellikle belirli bir durumda (baz durumu olarak adlandırılır) sona eren bir döngü oluşturur. Rekürsiyon, belirli türdeki problemleri çözmek için özellikle kullanışlıdır, özellikle de problemin doğal olarak daha küçük alt problemlere bölünebileceği durumlar.

Bir rekürsif fonksiyon genellikle iki ana bölüme ayrılır:

Baz durumu: Bu, rekürsiyonun sona ermesini sağlayan koşuldur. Rekürsif fonksiyonun bir noktada sonlanması gerektiğini belirler. Bu olmazsa, fonksiyon sürekli olarak kendisini çağırır ve bir döngü oluşturur.

Rekürsif durum: Bu, fonksiyonun kendisini çağırdığı bölümdür. Genellikle, bu bölümdeki çağrılar daha küçük bir alt probleme karşılık gelir.

Örneğin, bir sayının faktöriyelini hesaplayan bir rekürsif Python fonksiyonunu düşünün:

n! = { n = 0 ise 1

          Eğer n ≥ 1 ise n ·(n−1)·(n−2)··· 3 · 2 · 1

def factorial(n):
    if n == 0:         # Base case
        return 1
    else:              # Recursive case
        return n * factorial(n - 1)

Bu kodda, n == 0 olma durumu baz durumudur. Bu durum, rekürsiyonun sona erdiği ve sonucun döndürüldüğü yerdir.

Rekürsif durum ise n * factorial(n - 1). Bu ifade, n sayısının faktöriyelini hesaplarken daha küçük bir problem olan (n - 1) faktöriyeli hesaplama problemini çözüyor.

Rekürsiyon izlemesi, bir rekürsif fonksiyonun nasıl çalıştığını anlamak için kullanılan bir tekniktir. Bu süreç, bir fonksiyon çağrısının adım adım nasıl yürütüldüğünü ve hangi değerlerin döndürüldüğünü izlemenizi sağlar.

Örnek olarak, Yukardaki faktöriyel hesaplama fonksiyonunu düşünelim:

Faktöriyeli hesaplanacak bir sayı olan 3'ü bu fonksiyona parametre olarak verelim. Rekürsiyon izlemesi aşağıdaki şekilde olacaktır:

factorial(3) çağrılır:3 * factorial(2) hesaplanması gerekmektedir, bu yüzden factorial(2) çağrılır:

      2 * factorial(1) hesaplanması gerekmektedir, bu yüzden factorial(1) çağrılır:

              1 * factorial(0) hesaplanması gerekmektedir, bu yüzden factorial(0) çağrılır:

                     factorial(0) baz durumu olduğu için direkt olarak 1 döndürülür.

        factorial(1) sonucu 1 * 1 = 1 olarak hesaplanır ve döndürülür.

    factorial(2) sonucu 2 * 1 = 2 olarak hesaplanır ve döndürülür.

factorial(3) sonucu 3 * 2 = 6 olarak hesaplanır ve döndürülür.

Bu izleme süreci, rekürsiyonun derinlemesine nasıl çalıştığını gösterir: fonksiyon, her bir alt problemi çözene kadar kendini çağırır, daha sonra her bir alt problemin sonucunu kullanarak yukarı doğru geri döner ve nihai sonucu hesaplar.

Baz durumuna ulaşana kadar her rekürsif çağrının bir öncekinden daha küçük bir problemi çözdüğüne dikkat edin. Bu, rekürsiyonun her zaman sona ereceğini garantiler. Eğer bu olmasaydı, fonksiyon kendini sonsuz bir döngüde çağırır ve program asla durmaz.

Rekürsiyon, başta kafa karıştırıcı görünebilir, ancak belirli problemler için çok etkili bir çözüm sunar. Bir dizi, bir ağaç veya bir grafik gibi veri yapılarında dolaşmak veya matematiksel hesaplamalar (faktöriyel, Fibonacci sayıları, kuvvet hesaplama vb.) gibi problemleri çözmek için sıkça kullanılır. Ancak, doğru kullanılmadığında, sonsuz döngülere veya hafıza sorunlarına yol açabilir, bu yüzden dikkatli olunmalıdır.

"Drawing an English Ruler" (Bir İngiliz cetvelinin çizimi) genellikle bir rekürsiyon örneği olarak kullanılır. İngiliz cetveli, farklı uzunluklarda çizgilerden oluşan bir ölçü birimidir. Her bir inç, daha kısa olan birkaç çizgi ile bölünür ve bu çizgilerin uzunlukları genellikle rekürsif bir desen izler.

Bir İngiliz cetvelinin 2 inçini aşağıdaki gibi bir desenle çizelim:

- 0
--
- 1
--
- 2

Her bir inç (0, 1 ve 2), kısa bir çizgi (-) ve daha uzun bir çizgi (--) ile temsil edilir. İlgili rakam (inç) en uzun çizginin üzerinde yer alır.

Bu tür bir cetveli çizmek, bir rekürsiyon problemi olarak düşünülebilir çünkü her inçin çizimindeki desen, daha küçük bir ölçekte yinelenir.

Bir İngiliz cetveli çizimi yapmak için Python'da rekürsiyonu kullanabiliriz:

def draw_line(tick_length, tick_label=''):
    """Çizgi çiz ve numarayı yaz"""
    line = '-' * tick_length
    if tick_label:
        line += ' ' + tick_label
    print(line)

def draw_interval(center_length):
    """center_length merkez çizginin boyutunu belirtir"""
    if center_length > 0:                   # durma durumu, uzunluk 0 olduğunda
        draw_interval(center_length - 1)    # solunda çizgiler çiz
        draw_line(center_length)            # merkez çizgisini çiz
        draw_interval(center_length - 1)    # sağındaki çizgileri çiz

def draw_ruler(num_inches, major_length):
    """num_inches, kaç inç çizileceğini, major_length ise ana çizgilerin uzunluğunu belirtir"""
    draw_line(major_length, '0')            # cetvelin başındaki çizgiyi çiz
    for j in range(1, 1 + num_inches):
        draw_interval(major_length - 1)     # iç çizgileri çiz
        draw_line(major_length, str(j))     # inç çizgilerini çiz

# 2 inçlik bir İngiliz cetvelini çizelim
draw_ruler(2, 3)

Bu kodda, draw_line fonksiyonu bir çizgi çizer ve draw_interval fonksiyonu verilen uzunluktaki bir çizgi dizisini çizer. Bu iki işlem, draw_ruler fonksiyonunda rekürsif olarak kullanılır, böylece bir İngiliz cetveli çizilir.

"Recursion Run Amok" (Rekürsyonun Kontrolden Çıkması), rekürsyonun yanlış veya dikkatsizce kullanıldığı durumları tanımlar. Bu, genellikle iki ana şekilde gerçekleşir: sonlandırma durumu olmadan rekürsyon yapmak veya çok fazla rekürsyon derinliğine sahip olmak.

1. Sonlandırma Durumu Olmadan Rekürsyon: Her rekürsyon çağrısının sonunda bir sonlandırma durumunun olması gereklidir. Sonlandırma durumu, rekürsyonun bir noktada duracağını ve daha fazla kendini çağırmayacağını belirtir. Eğer bir sonlandırma durumu yoksa, fonksiyon sürekli olarak kendisini çağırır ve program asla bitmez. Bu durum genellikle bir hata veya döngüye neden olur.

2. Çok Fazla Rekürsyon Derinliği: Her rekürsyon çağrısı, çağrı yığınında yeni bir kare oluşturur. Bu, çağrının sonunda temizlenmek üzere bilgi saklar. Ancak, yığın sınırlı bir boyuttadır ve çok fazla rekürsyon çağrısı yığını doldurabilir. Bu durum, genellikle bir 'maximum recursion depth exceeded' hatası ile sonuçlanır. Yığın taşması genellikle çok büyük girdilerle veya kötü tasarlanmış bir rekürsyonla meydana gelir.

Rekürsyonun kontrolden çıkmaması için, her zaman bir sonlandırma durumuna sahip olmalı ve gereksiz yere çok derin rekürsyonlardan kaçınmalısınız. Dikkatli bir şekilde kullanıldığında, rekürsyon karmaşık problemlerin çözümünü çok daha basit ve anlaşılır hale getirebilir. Ancak yanlış kullanıldığında, hafıza sorunlarına ve beklenmeyen davranışlara neden olabilir.

Fibonacci sayıları, bir önceki iki sayının toplamı olan bir dizi sayıdır. İlk 10 Fibonacci sayısı: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.

Bu diziye dayanarak, bir Fibonacci sayısını hesaplamak için aşağıdaki rekürsif formülü kullanabiliriz:

Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) 

Ancak, bu yöntem birçok gereksiz hesaplama yapar. İki ayrı rekürsif çağrı yaparak, birçok Fibonacci sayısını birden çok kez hesaplarız. Örneğin, Fibonacci(5) hesaplamak için, Fibonacci(4) ve Fibonacci(3) hesaplamamız gerekir. Ancak, Fibonacci(4) hesaplarken, Fibonacci(3) ve Fibonacci(2) hesaplarız. Yani, Fibonacci(3)'ü iki kere hesaplıyoruz - bir kere Fibonacci(5) ve bir kere Fibonacci(4) için.

Bu problem, n büyüdükçe daha da büyür. Fibonacci(n) hesaplamak için yaklaşık 2^n işlem yaparız, bu da n'in büyüklüğü için oldukça yavaş bir işlem olabilir.

Bu verimsizlik, "An Inefficient Recursion for Computing Fibonacci Numbers" yani "Fibonacci Sayılarını Hesaplamak için Verimsiz Bir Rekürsyon" ifadesi ile anlatılır.

Bu problemi çözmek için, önceden hesaplanan sonuçları saklayan ve yeniden kullanabilen bir teknik olan "dinamik programlama" kullanılabilir. Dinamik programlama, Fibonacci sayılarını hesaplamanın en etkin yoludur ve bu gereksiz hesaplamaları önler.

Fibonacci dizisi için daha etkili bir hesaplama yöntemi "dinamik programlama" kullanmaktır. Dinamik programlama, daha önce hesaplanan sonuçları saklar ve tekrar tekrar aynı hesaplamaları yapmaktan kaçınır. Bu, özellikle Fibonacci gibi bir önceki sonuçlara dayanan işlemler için yararlıdır.

Python'da, bu durumu bir örnek üzerinden göstermek gerekirse:

def fibonacci(n):
    fib = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]

Bu kod, n'inci Fibonacci sayısını hesaplamak için bir dizi oluşturur. Dizinin ilk iki öğesi, Fibonacci dizisinin ilk iki öğesi olan 0 ve 1'dir. Sonra, her i için, fib'yi fib[i - 1] ve fib[i - 2]'nin toplamı olarak hesaplar.

Bu şekilde, her Fibonacci sayısını sadece bir kez hesaplar ve daha sonra ihtiyaç duyulduğunda bu sonucu yeniden kullanır. Bu, gereksiz hesaplamaları önler ve Fibonacci sayılarını hesaplamanın daha verimli bir yolunu sağlar. n'inci Fibonacci sayısını hesaplarken bu algoritma O(n) karmaşıklığında çalışır ki bu da önceki sürümüne göre çok daha hızlıdır.

Python'da, rekürsif fonksiyonların ne kadar derinliğe gidebileceğini belirleyen bir sınırlama vardır. Bu, "maksimum rekürsif derinlik" veya "maksimum rekürsif sınır" olarak adlandırılır.

Python, bir fonksiyonun kendisini çok fazla kez çağırmasını engellemek için bu sınırlamayı kullanır. Çünkü çok fazla rekürsif çağrı, büyük miktarda bellek kullanabilir ve programınızın çökmesine neden olabilir.

Python'da varsayılan maksimum rekürsif derinlik genellikle 1000'dir. Ancak bu değer, kullanılan işletim sistemine ve Python yorumlayıcısının ayarlarına bağlıdır.

Python'daki maksimum rekürsif derinliği öğrenmek için sys modülünü kullanabilirsiniz:

import sys
print(sys.getrecursionlimit())

Maksimum rekürsif derinliği değiştirmek için, aşağıdaki gibi sys.setrecursionlimit(limit) fonksiyonunu kullanabilirsiniz:

import sys
sys.setrecursionlimit(3000)

Ancak bu sınırlamayı artırmanın bellek kullanımında bir artışa neden olacağını unutmamak önemlidir. Genellikle, rekürsif derinliği çok fazla artırmaktansa, problemi çözmek için daha verimli bir algoritma veya yöntem bulmayı düşünmek daha iyidir.