Bu makalede, özyinelemeli işlevler oluşturmayı öğreneceksiniz; kendini çağıran bir işlev. Ayrıca, kuyruk özyinelemeli işlevi hakkında bilgi edineceksiniz.
Kendini çağıran bir işlev özyinelemeli işlev olarak bilinir. Ve bu teknik, özyineleme olarak bilinir.
Fiziksel bir dünya örneği, iki paralel aynayı birbirine bakacak şekilde yerleştirmek olacaktır. Aralarında bulunan herhangi bir nesne özyinelemeli olarak yansıtılır.
Özyineleme programlamada nasıl çalışır?
fun main (args: Array) (… recurse ()…) fun recurse () (… recurse ()…)
Burada recurse()işlev, işlev gövdesinin recurse()kendisinden çağrılır . Bu program şu şekilde çalışır:
Burada, yinelemeli çağrı sonsuza kadar devam ederek sonsuz özyinelemeye neden olur.
Sonsuz özyinelemeden kaçınmak için, if … else (veya benzeri bir yaklaşım), bir dalın özyinelemeli çağrıyı yaptığı ve diğerinin yapmadığı durumlarda kullanılabilir.
Örnek: Özyineleme kullanarak bir Sayının faktöriyelini bulun
fun main(args: Array) ( val number = 4 val result: Long result = factorial(number) println("Factorial of $number = $result") ) fun factorial(n: Int): Long ( return if (n == 1) n.toLong() else n*factorial(n-1) )
Programı çalıştırdığınızda, çıktı:
4 = 24 faktöriyeli
Bu program nasıl çalışır?
factorial()Fonksiyonun özyinelemeli çağrısı aşağıdaki şekilde açıklanabilir:
İşte ilgili adımlar:
factorial (4) // 1. fonksiyon çağrısı. Argüman: 4 4 * factorial (3) // 2. fonksiyon çağrısı. Argüman: 3 4 * (3 * factorial (2)) // 3. fonksiyon çağrısı. Argüman: 2 4 * (3 * (2 * factorial (1))) // 4. fonksiyon çağrısı. Bağımsız Değişken: 1 4 * (3 * (2 * 1)) 24
Kotlin Kuyruk Özyinelemesi
Kuyruk özyineleme, Kotlin dilinin özelliğinden ziyade genel bir kavramdır. Kotlin dahil olmak üzere bazı programlama dilleri, yinelemeli çağrıları optimize etmek için kullanır, oysa diğer diller (örn. Python) bunları desteklemez.
Kuyruk özyinelemesi nedir?
Normal özyinelemede, önce tüm özyinelemeli çağrıları gerçekleştirirsiniz ve en sonunda dönüş değerlerinden sonucu hesaplarsınız (yukarıdaki örnekte gösterildiği gibi). Bu nedenle, tüm özyinelemeli çağrılar yapılana kadar sonuç almazsınız.
Kuyruk özyinelemede, önce hesaplamalar yapılır, ardından özyinelemeli çağrılar yürütülür (özyinelemeli çağrı, geçerli adımınızın sonucunu bir sonraki özyinelemeli çağrıya geçirir). Bu, özyinelemeli çağrıyı döngüye eşdeğer hale getirir ve yığın taşması riskini önler.
Kuyruk özyineleme koşulu
Özyinelemeli bir işlev, kendisine yapılan işlev çağrısı gerçekleştirdiği son işlemse, kuyruk özyineleme için uygundur. Örneğin,
Örnek 1: Kendi kendine işlev çağrısı n*factorial(n-1)son işlem olmadığından kuyruk özyineleme için uygun değil.
fun factorial (n: Int): Long (if (n == 1) (return n.toLong ()) else (return n * factorial (n - 1)))
Örnek 2:fibonacci(n-1, a+b, a) Son işlem kendisine işlev çağrısı olduğu için kuyruk özyinelemeye uygun .
fun fibonacci (n: Int, a: Long, b: Long): Long (return if (n == 0) b else fibonacci (n-1, a + b, a))
Derleyiciye Kotlin'de kuyruk özyineleme gerçekleştirmesini söylemek için, işlevi tailrecdeğiştirici ile işaretlemeniz gerekir .
Örnek: Kuyruk Özyineleme
import java.math.BigInteger fun main(args: Array) ( val n = 100 val first = BigInteger("0") val second = BigInteger("1") println(fibonacci(n, first, second)) ) tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger ( return if (n == 0) a else fibonacci(n-1, b, a+b) )
Programı çalıştırdığınızda, çıktı:
354224848179261915075
Bu program 100 hesaplar inci Fibonacci serisinin terimini. Çıktı çok büyük bir tam sayı olabileceğinden, BigInteger sınıfını Java standart kitaplığından içe aktardık.
Burada, işlev değiştirici fibonacci()ile işaretlenmiştir tailrecve işlev, kuyruk özyinelemeli çağrı için uygundur. Bu nedenle, derleyici bu durumda özyinelemeyi optimize eder.
Kuyruk özyinelemesini kullanmadan Fibonacci serisinin 20000'inci terimini (veya başka bir büyük tamsayıyı) bulmaya çalışırsanız , derleyici java.lang.StackOverflowErroristisna atacaktır . Ancak, yukarıdaki programımız gayet iyi çalışıyor. Bunun nedeni, geleneksel özyineleme yerine verimli döngü tabanlı sürüm kullanan kuyruk özyinelemeyi kullanmış olmamızdır.
Örnek: Kuyruk Özyinelemesini Kullanan Faktöriyel
Yukarıdaki örnekte (ilk örnek) bir sayının faktöriyelini hesaplama örneği, kuyruk özyinelemesi için optimize edilemez. İşte aynı görevi gerçekleştirmek için farklı bir program.
fun main(args: Array) ( val number = 5 println("Factorial of $number = $(factorial(number))") ) tailrec fun factorial(n: Int, run: Int = 1): Long ( return if (n == 1) run.toLong() else factorial(n-1, run*n) )
Programı çalıştırdığınızda, çıktı:
5 = 120 faktöriyeli
Özyinelemeli işlev kuyruk özyinelemeye uygun olduğundan derleyici bu programdaki özyinelemeyi optimize edebilir ve tailrecderleyiciye özyinelemeyi optimize etmesini söyleyen değiştirici kullandık .
