Recursion merupakan sebuah konsep dimana sebuah fungsi memanggil
dirinya sendiri, recursion banyak dipakai pada bahasa fungsional
bersih, namun dapat dipakai juga pada bahasa lain yang bukan bahasa
fungsional bersih.
contoh recursion dalam bahasa Haskell, yang akan menghitung factorial :
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
dari fungsi diatas kita dapat melihan bila kondisi atau variable n
adalah 0 maka akan mengembalikan anggak 1 dan akan keluar dari
recursion, dan jika nilai n bukan lah 0 maka fungsi ini akan memanggil
dirinya sendiri dengan perubahan pada parameter n, seperti inilah
bahasa yang tidak memiliki fungsi loop seperti while, for loop dapat
melakukan looping, namun cara ini merupakan cara yang sangat buruk
untuk melakukan loop, cara recursion seperti ini merupakan cara yang
sangat tidak efisien karna setiap kali fungsi memanggil diri sendiri
maka ada kemungkinan memori stack kita penuh, dan dapat terjadi Error
stack overflow.
seperti inilah ilustrasinya, jika kita memasukan angka 5 pada input
fungsi factorial :
factorial 5 = 5 * factorial ( 5 - 1 )
factorial 4 = 4 * factorial ( 4 - 1 )
factorial 3 = 3 * factorial ( 3 - 1 )
factorial 2 = 2 * factorial ( 2 - 1 )
factorial 1 = 1 * factorial ( 1 - 1 )
factorial 0 = 1
-- then
factorial 5 = 5 * 4 * 3 * 2 * 1
seperti visualisasi diatas fungsi factorial akan menunggu dan
memmanggil dirinya sendiri sampai memenuhi nilai 0, setelah itu akan
kembali lagi ke awal, bayangkan saja bila kita memasukan nilai 100
untuk inputnya, maka fungsi factorial akan memanggil 100x dirinya
sendiri, dan ada kemungkinan akan terjadi stack ovewflow karna memori
stack penuh akibat fungsi factorial
Tail Recursionn
Tail recursion juga merupakan sebuah tehnik recursion tetapi cara tail
recursion melakukan recursion sangat lah berbeda dari recursion biasa,
dan juga lebih efisien.
seperti inilah kita melakukan sebuah tail recursion :
factorial :: (Eq t, Num t) => t -> t
factorial n = go n 1
go :: (Eq t, Num t) => t -> t -> t
go 1 a = a
go n a = go ( n - 1 ) ( a * n )
bisa dilihat kode diatas bahwa kita memerlukan 2 buah fungsi, fungsi
untuk memanggil dan fungsi yang akan melakukan perhitungan, jika saya
memberikan angka 5 ke dalam fungsi factorial maka seperti inilah
kalkulasinya :
factorial 5 = go 5 1
= go 4 5 -- go ( 5 - 1 ) ( 5 * 1 )
= go 3 20 -- go ( 4 - 1 ) ( 4 * 5 )
= go 2 60 -- go ( 3 - 1 ) ( 3 * 20 )
= go 1 120 -- go ( 2 - 1 ) ( 60 * 2 )
dari visualisasi diatas kita dapat melihat bahwa fungsi factorial
hanya memanggil fungsi go sekali sampai parameter n yang ada di go
menjadi 1 dan menggembalikan variable a yaitu 120, maka dalam fungsi
go parameter n merupakan parameter tujuan dan parameter a merupakan
tempat kita melakukan perhitungan, dengan melakukan recursion seperti
ini kita bisa menghindari stack overflow karna kita hanya memanggil 2
fungsi saja.