Elixir u praksi: Implementiranje rekurzije

U informatici rekurzija je metoda gde rešenje problema zavisi od rešenja manjih istanci istog problema.

Ovo je poprilično apstraktno i široko objašnjenje koje nudi Wikipedia, pa hajde da probamo da ga jednostavnije objasnimo na sledeći način:

Rekurzija je pozivanje funkcije unutar te iste funkcije.

Rekurzija je implementirana u većini popularnih jezika — Java, Python, Ruby, između ostalih — ali sam se ja bavio njome najviše u Elixiru o kom smo pisali, tako da će primeri u ovom postu biti primereni njemu.

Suprotno od iteracije što bi se koristilo jeste rekurzija. To su “for” i “while” petlje. Zašto koristiti rekurziju umesto iteracije?

Mnogo je čitljivije od “for” petlje;

Manja verovatnoća za greške;

Manje kôda za istu stvar koji biste uradili sa klasičnom iteracijom;

Generalno ako se bavite funkcionalnim programiranjem rekurzija je mnogo brža i jeftinija po pitanju resursa. Ali ako pišete, na primer, Javu, verovatno se više isplati klasična iteracija.

Neretko ćete naći rekurziju spomenutu uz termine kao što je “binarno stablo” — ovde nećemo ići u detalje ali vas ohrabrujem da potražite više o ovome, jer je tema izuzetno zanimljiva.

Vreme je za par praktičnih primera. Hajde da napišemo modul koji ćemo nazvati “MyList”  i imaće dve funkcije za manipulaciju sa listama.

Prva funkcija će da primi listu brojeva i da vrati listu brojeva gde je svaki broj kvadrat broja koji je primljen.

```

defmodule MyList do

def square([]) do

[]

end

def square([ head | tail ]) do

[ head * head | square(tail) ]

end

end

```

Nekoliko stvari se dešava u kôdu iznad. Prvo, imamo dve funkcije koje imaju isto ime — ovo zato što Elixir može da na osnovu paramatera odluči koju funkciju da pozove. Parametar u drugoj funkciji očekuje listu sa elementima i onda Elixir “razdvoji” listu na “glavu” (prvi elemenat u listi) i na “rep” (svi ostali elementi).

Hajde da ovo probamo ovo u komandnoj liniji:

```

$ iex my_list.exs

iex > MyList.square([3, 4, 5])

# => [ 9, 16, 25 ]

```

Radi! Ali kako ?

```

# prvi put kad se pozove funkcije radi se komparacija na osnovu parametara

# i poziva se druga “square” funkcija, jer prva samo prima praznu listu

[ 3*3 | square([4, 5]) ]

# U sledećem pozivu opet se radi komparacija

# I ista funkcija je izabrana

[ 4*4 | square([5]) ]

# I tako se poziva ta ista funkcija dok god rezultat poziva nije prazna lista

# nakon čega se vrši kalkulacija

```

Elixir koristi closure. U programskim jezicima gde je funkcija bitan faktor (Javascript, Elixir, Ruby ), “closure” predstavlja tehniku gde ako imamo funkciju u funkciji unutrašnja funkcija ima pristup vrednostima i okruženju prve funkcije.

Vreme je za još jednu funkciju u našem modulu, a ta funkcija će se zvati “map”. Ta funkcija je poprilično popularna u svetu funkcionalnog programiranja i ono što radi jeste da prima kao argumente listu i funkciju, gde je rezultat funkcije nova lista gde je na svaki elemenat te liste primenjena funkcija koje je primljena kao argument.

Zvuči komplikovano ali zapravo nije.

```

def map([], _func) do

[]

end

def map([head | tail], func) do

[ func.(head) | map(tail, func) ]

end

```

“map” funkcija je poprilično slična “square” funkciji koju smo prethodno napisali, ali je razlika u sledecoj liniji:

```

func.(head)

```

U Elixiru to je poziv anonimne funkcije.

Hajde da probamo ovo opet u komandnoj liniji:

```

iex > MyList.map([1, 2, 3], fn(n) -> n + 1 end)

# => [2, 3, 4]

```

Vežbe radi možete napisati kako “map” funkcija radi na papiru, nešto slično smo uradili malo pre sa “square” funkcijom.