Rekurzivne funkcije
===================

Jedna od osobina funkcija je mogućnost pozivanja drugih funkcija. Samim tim, ako funkcije mogu pozivati druge funkcije, šta se dešava ukoliko funkcije pozivaju same sebe? Programerski koncept u kojem funkcije pozivaju same sebe naziva se **rekurzija**, a takve funkcije nazivaju se **rekurzivne funkcije**. Iako na prvi pogled može djelovati zbunjujuće, rekurzija je moćan alat koji omogućava elegantno rješavanje problema razbijanjem na manje, slične podprobleme.

Jednostavan primjer iz svakodnevnog života može pomoći u razumijevanju ovog koncepta. Rekurzija će biti razmotrena na primjeru pripreme ispita. Ukoliko se cijeli ispit posmatra kao kompleksna cjelina, može djelovati previše zahtjevno. Međutim, podjelom gradiva na manje dijelove koje treba naučiti, proces postaje jednostavniji. Onda se i ti dijelovi mogu dodatno podijeliti na još manje cjeline, sve dok se ne dođe do pojedinačnih lekcija koje je lakše savladati. Ovaj princip razlaganja problema na manje dijelove, koji se ponavlja do trivijalnih zadataka, u osnovi je rekurzije.

Jedan od najjednostavnijih matematičkih primjera rekurzije je izračunavanje faktorijela broja. Faktorijel broja `n` definisan je kao `n! = n * (n-1) * (n-2) * ... * 1`. Drugačije zapisano, može se reći da je `n! = n * (n-1)!`. Međutim, tada je `(n-1)! = (n-1)*(n-2)!` i ovaj postupak se može nastaviti. Na primjeru broja 5, vrijedi da je `5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 3 * 2 * 1 * 0!`. Jasno je da je ovdje neophodno zaustaviti proces, jer je vrijednost `0!` poznata i iznosi 1. Ovaj izraz se naziva **baznim slučajem**.

U primjeru iznad, izračunavanje faktorijela svodi se na isti zadatak izračunavanja faktorijela za manji broj, sve dok se proces ne svede do baznog slučaja kada je faktorijel broja 0 definisan kao 1.

Ispod je primjer koda u kojem se navedeni postupak zapisuje u obliku rekurzivne funkcije.

def faktorijel(n):
    if n == 0:
        return 1
    else:
        return n * faktorijel(n - 1)

print(faktorijel(5))  # 120

Kada se funkcija `faktorijel(5)` pozove, pokreće se lanac rekurzivnih poziva koji rade na principu "odgode" konačnog rješenja dok se ne dođe do baznog slučaja.

Prvi poziv, `faktorijel(5)`, ne može odmah vratiti rezultat jer zahtijeva izračun `faktorijel(4)`. Slično tome, `faktorijel(4)` poziva `faktorijel(3)`, i ovaj niz se nastavlja sve dok se ne dođe do `faktorijel(0)`. U tom trenutku, funkcija prepoznaje bazni slučaj (`if n == 0`) i vraća vrijednost 1.

Kada se dostigne bazni slučaj, rekurzivni pozivi se počinju "odmotavati" u obrnutom redoslijedu. Svaki povratak iz funkcije množi rezultat prethodnog poziva:

- `faktorijel(1)` vraća `1 * 1 = 1`
- `faktorijel(2)` vraća `2 * 1 = 2`
- `faktorijel(3)` vraća `3 * 2 = 6`
- `faktorijel(4)` vraća `4 * 6 = 24`
- `faktorijel(5)` vraća `5 * 24 = 120`

Na kraju, rezultat poziva `faktorijel(5)` je 120, što predstavlja konačni rezultat izračuna. Ovaj primjer jasno pokazuje kako se problem svodi na manje verzije samog sebe sve dok se ne dođe do baznog slučaja.

## Struktura rekurzivne funkcije

Rekurzivne funkcije imaju prepoznatljivu strukturu koja se sastoji od nekoliko ključnih elemenata. Da bi rekurzija ispravno radila i dovela do rješenja problema, svaka funkcija mora imati:

1. **Bazni slučaj** (eng. *base case*) – Ovo je uslov koji zaustavlja dalju rekurziju. Kada se dostigne bazni slučaj, funkcija vraća rezultat bez dodatnih rekurzivnih poziva.
2. **Rekurzivni slučaj** (eng. *recursive case*) – Ovo je dio funkcije u kojem funkcija poziva samu sebe s manjim ili pojednostavljenim problemom.
3. **Smanjenje problema** – Sa svakim rekurzivnim pozivom, problem mora postajati jednostavniji kako bi se osiguralo da će se funkcija u nekom trenutku svesti na bazni slučaj.

Ova tri elementa su ključ za ispravnu i efikasnu rekurzivnu funkciju. Ako nedostaje bilo koji od njih, rekurzija može rezultirati greškama poput beskonačnih poziva ili prekoračenja steka (eng. *stack overflow*).

## Osnovna forma rekurzivne funkcije

U nastavku će biti navedena osnovna forma rekurzivnih funkcija.

def rekurzivna_funkcija(parametar):
    if bazni_slucaj(parametar):
        return trivijalno_rjesenje
    else:
        manji_problem = transformacija(parametar)
        return kombinacija(rekurzivna_funkcija(manji_problem))

U osnovnoj formi rekurzivne funkcije, važno je prepoznati komponente baznog slučaja, transformacije i kombinacije:
- **`bazni_slucaj`** – Provjerava da li je dostignut najjednostavniji problem (zaustavni uslov).
- **`transformacija`** – Smanjuje složenost problema, približava ga baznom slučaju.
- **`kombinacija`** – Kombinuje rezultat trenutnog koraka s rezultatima rekurzivnih poziva.

### Primjer – Suma prvih `n` brojeva

Funkcija koja računa sumu prvih `n` prirodnih brojeva može se napisati rekurzivno kao u kodu ispod.

def suma(n):
    if n == 0:
        return 0
    else:
        return n + suma(n - 1)

Ova funkcija u potpunosti ilustruje ranije navedenu osnovnu strukturu rekurzivnih funkcija.

1. **Bazni slučaj** – Ako je `n == 0`, funkcija vraća `0`. To predstavlja najjednostavniji problem (trivijalno rješenje).
2. **Rekurzivni slučaj** – Ako `n > 0`, funkcija poziva samu sebe s `n-1`, smanjujući problem korak po korak.
3. **Smanjenje problema** – Svakim pozivom, vrijednost `n` se smanjuje dok se ne dostigne `0`.

Prilikom poziva `suma(5)`, funkcija se poziva sve dok `n` ne dostigne `0`. Nakon toga, svi pozivi se "odmotavaju", sabirajući brojeve od 1 do 5. U primjeru je jasno naveden bazni slučaj, transformacija koja poziva funkciju za `n-1` i kombinacija koja rezultat rekurzivnog poziva sabira sa brojem `n`.

## Prekoračenje steka i dubina rekurzije

Rekurzivne funkcije imaju nekoliko potencijalnih zamki za početnike. Kada rekurzivna funkcija poziva samu sebe previše puta bez zaustavljanja, može doći do greške koja se naziva **prekoračenje steka** (*stack overflow*). Ova greška znači da je program potrošio svu memoriju predviđenu za praćenje funkcija koje su trenutno u toku izvršavanja.

### Šta je stek (stack)?

Stek se u ovom kontekstu posmatra kao lista zadataka koje računar pamti dok izvršava program. Svaki put kada se pozove neka funkciju, računar je "stavlja" na vrh steka kako bi zapamtio šta funkcija treba da uradi i gdje treba da se vrati kada završi. Kada se funkcija završi, skida se s vrha steka i program nastavlja dalje.

U nastavku je primjer poziva za faktorijel:

1. Pozove se `faktorijel(5)` – stavlja se na stek.
2. `faktorijel(5)` poziva `faktorijel(4)` – dodaje se na stek.
3. `faktorijel(4)` poziva `faktorijel(3)` – dodaje se na stek.
4. Proces se nastavlja sve dok ne dođemo do `faktorijel(0)`.

Kada funkcija dostigne **bazni slučaj** (`faktorijel(0)`), sve funkcije se postepeno skidaju sa steka, dok program ne dobije konačni rezultat. U momentu kada se pozove bazni slučaj, na steku se već nalazi 6 poziva (od `faktorijel(5)` do `faktorijel(0)`), a ovaj broj može biti i značajno veći za različite funkcije. Ukoliko bi računali faktorijel nekog velikog prirodnog broja, stek bi sadržavao veliki broj elemeanta, što nije uvijek moguće podržati.

### Kako dolazi do greške?

Ako ne postoji ispravan uslov zaustavljanja rekurzije ili ako se jednostavno rekurzivna funkcija poziva previše puta (tzv. preduboka rekurzija), funkcije će se gomilati na steku bez kraja, sve dok računar ne ostane bez memorije predviđene za to.

def beskrajna_rekurzija(n):
    return beskrajna_rekurzija(n - 1)

beskrajna_rekurzija(1)

U primjeru iznad, program će neprestano dodavati pozive na stek dok ne dođe do greške `RecursionError: maximum recursion depth exceeded`. Greška se dešava, jer ne postoji bazni slučaj koji će se dostići i koji će prekinuti rekurzivne pozive.

### Kako izbjeći prekoračenje steka?

1. **Neophodan bazni slučaj** – Svaka rekurzivna funkcija mora imati jasan uslov koji zaustavlja dalju rekurziju.
2. **Ograničen broj poziva** – U Pythonu postoji ograničenje na broj rekurzivnih poziva (obično oko 1000). Ako se očekuje veći broj, ograničenje se može povećati, ali uz dodatni oprez.

import sys
sys.setrecursionlimit(2000)

3. **Korištenje iteracije umjesto rekurzije** – Mnoge rekurzivne funkcije mogu se napisati korištenjem `for` ili `while` petlji, što može biti efikasnije i sprječava gomilanje na steku, ali je često kod kompleksniji.

Dakle, stek se ponaša kao "lista zadataka" koje program mora izvršiti. Prekoračenje steka dešava se kada se na ovu listu doda previše zadataka zbog rekurzivnih poziva koji se ne zaustavljaju.

## Prednosti i mane rekurzivnih funkcija

Rekurzija je moćan alat u programiranju, ali njena primjena dolazi s određenim prednostima i manama. Razumijevanje ovih aspekata ključno je za pravilnu primjenu i izbor između rekurzivnih i iterativnih rješenja.

### Prednosti rekurzije

1. **Jednostavnost i čitljivost koda**
Rekurzivne funkcije često nude kraće i elegantnije rješenje problema u poređenju s iterativnim pristupima. Kod se može napisati na način koji direktno prati prirodnu rekurzivnu definiciju problema, čime se povećava čitljivost.

2. **Prirodno rješenje za rekurzivne probleme**
Određeni problemi, poput problema podijeli-pa-vladaj (*divide and conquer*), prirodno se rješavaju rekurzijom. Iterativna rješenja za takve probleme često su kompleksnija i teža za implementaciju. Kod ovakvih problema, po prirodi pristupa se problemi svode na više jednostavnijih problema istog tipa koji se jednostavnije rješavaju. Klasičan primjer rješenja podijeli-pa-vladaj je pretraga određenog prostora, gdje se pretraga velikog prostora može svesti na više manjih pretraga manjih prostora.

3. **Lakše upravljanje podproblemima**
Rekurzija često automatski eliminirap otrebu za potrebu za eksplicitnim održavanjem stanja i varijabli koje se javljaju u iterativnim verzijama programa.

4. **Smanjenje potrebe za pomoćnim varijablama**
U iterativnim rješenjima često su potrebne dodatne varijable i strukture podataka za praćenje stanja. Rekurzija često može eliminisati potrebu za tim varijablama, čineći kod jednostavnijim i direktnijim.

### Mane rekurzije

1. **Veća potrošnja memorije**
Svaki rekurzivni poziv zauzima mjesto na steku poziva. Za duboke rekurzije, ovo može dovesti do ranije pomenutog prekoračenja steka. Iterativna rješenja često koriste manje memorije, jer nemaju slojevite pozive funkcija.

2. **Sporije izvršavanje**
Rekurzivne funkcije često imaju veći vremenski trošak zbog velikog broja poziva funkcija i vraćanja rezultata. U iterativnim rješenjima, petlje često obavljaju istu operaciju efikasnije, bez dodatnog troška poziva funkcija.

3. **Mogućnost beskonačne rekurzije**
Ako bazni slučaj nije pravilno definisan ili ako rekurzija ne smanjuje problem prema baznom slučaju, funkcija može ući u beskonačnu petlju, što dovodi do prekida programa.

4. **Teža optimizacija**
Iterativni algoritmi se lakše optimizuju za brzinu i memoriju, dok rekurzivni algoritmi često zahtijevaju dodatne tehnike poput memorisanja (*memoization*) ili dinamičkog programiranja kako bi postigli istu efikasnost.

5. **Ograničena dubina steka**
U nekim jezicima, maksimalna dubina steka je ograničena, što ograničava broj rekurzivnih poziva koji se mogu obaviti. Ovo može biti problem kod velikih ulaznih vrijednosti.

:::info
### Kada koristiti rekurziju?

Rekurzija je posebno korisna kada problem ima prirodnu rekurzivnu strukturu, kao što su grafovi ili algoritmi podijeli-pa-vladaj. U takvim situacijama, rekurzivni pristup omogućava da se problem elegantno podijeli na manje podprobleme, čime se olakšava njegovo rješavanje. Kod koji koristi rekurziju često je kraći i jasniji, što doprinosi boljoj čitljivosti i održavanju programa. Takođe, kada dubina rekurzije nije velika, rizik od prekoračenja steka je minimalan, što omogućava stabilno izvršavanje koda bez dodatne optimizacije. Rekurzija se često koristi kada je primarni cilj pronaći rješenje problema, dok optimizacija performansi nije od ključnog značaja.

Ipak, postoje situacije u kojima je bolje izbjegavati rekurziju. Kada problem može biti riješen iterativno na jednostavniji i efikasniji način, iterativno rješenje često donosi bolje performanse i manju potrošnju memorije. U slučajevima gdje rekurzija rezultira dubokim stekom poziva, može doći do preopterećenja memorije i prekoračenja steka, što može dovesti do prekida programa. Ako je performansa ključna, iterativna rješenja su obično brža i optimizovanija, posebno kada se radi o velikim ulazima ili intenzivnim algoritmima. Zbog toga je važno pažljivo razmotriti kada koristiti rekurziju kako bi se izbjegli potencijalni problemi vezani za efikasnost i resurse sistema.
:::

## Rekurzija s više poziva – Fibonačijev niz

Kod jednostavnih rekurzivnih funkcija, kao što je faktorijel, funkcija obično ima jedan bazni slučaj i jedan rekurzivni poziv. Međutim, česti su problemi gdje rekurzivna funkcija poziva samu sebe **više puta** unutar istog tijela funkcije. Ovi slučajevi su kompleksniji i često zahtijevaju **više baznih slučajeva** kako bi se osiguralo ispravno zaustavljanje rekurzije.

Jedan od klasičnih primjera je izračunavanje **Fibonačijevog niza**.

### Šta je Fibonačijev niz?
Fibonačijev niz je sekvenca brojeva u kojoj je:
- Svaki broj jednak **zbiru prethodna dva broja** u nizu.
- Prva dva broja u nizu su uvijek `0` i `1`.

Matematički, niz se definiše na sljedeći način:
- F(0) = 0, F(1) = 1
- F(n) = F(n-1) + F(n-2) za n ≥ 2

U definiciji iznad, navedeno je da su prva dva elementa niza 0 i 1 (nulti i prvi element), te rekurzivna definicija u kojoj je svaki naredni element jednak zbiru prethodna dva. Time se dobija niz 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

### Rekurzivna implementacija
Rekurzivna funkcija za izračunavanje `n`-tog Fibonačijevog broja može se zapisati ovako:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

print(fib(6))  # 8

Ova funkcija sadrži dva bazna slučaja i rekurzivni poziv.

1. **Dva bazna slučaja**:
- Ako je `n == 0`, funkcija vraća `0` (prvi Fibonačijev broj).
- Ako je `n == 1`, funkcija vraća `1` (drugi Fibonačijev broj).

2. **Rekurzivni slučaj**:
- Ako je `n >= 2`, funkcija se poziva **dva puta**:

     return fib(n-1) + fib(n-2)

- Ovdje funkcija traži prethodna dva Fibonačijeva broja i sabira ih kako bi dobila `n`-ti broj.

#### Zašto su potrebna **dva bazna slučaja**?
Kada se pišu rekurzivne funkcije, ključno je pravilno definisati bazne slučajeve kako bi se spriječile greške i osiguralo da funkcija radi ispravno. Kod funkcije koja računa Fibonačijeve brojeve, prisustvo **dva bazna slučaja** (`n == 0` i `n == 1`) je neophodno kako bi funkcija pravilno rješavala sve pozive i izbjegla nelogične situacije.

Ako bi Fibonači funkcija imala samo jedan bazni slučaj, na primjer `n == 0`, program bi mogao naići na problem prilikom poziva `fib(-1)`. Ovakav scenario nema matematičkog smisla i rezultovao bi greškom ili, u najgorem slučaju, **beskonačnom rekurzijom** koja bi dovela do prekoračenja steka.

Slučaj se dešava pri pozivu `fib(2)`:

fib(2) = fib(1) + fib(0)

U ovom primjeru, poziv `fib(1)` dolazi do izražaja. Da nije definisan bazni slučaj za `n == 1`, funkcija bi nastavila dalje da računa:

fib(1) = fib(0) + fib(-1)

Međutim, poziv `fib(-1)` bi bio neispravan i program bi nastavio da poziva negativne vrijednosti `n` u nedogled. Ovakav proces brzo bi doveo do beskonačne rekurzije i rezultirao greškom.

Prisutnost **dva bazna slučaja** (`n == 0` i `n == 1`) osigurava da funkcija uvijek može pravilno odgovoriti na pozive za najmanje vrijednosti `n` i time zaustaviti rekurziju. Kada funkcija dođe do `fib(0)`, vraća `0`, a kada dođe do `fib(1)`, vraća `1`. Ovaj mehanizam sprječava dalji rekurzivni poziv ka negativnim brojevima i garantuje da se rekurzija **uvijek završava**.

Osim što su spriječene greške, dva bazna slučaja čine funkciju **matematički ispravnom** i omogućavaju tačno računanje Fibonačijevih brojeva za sve nenegativne vrijednosti `n` u skladu sa matematičkom definicijom niza.

### Vizualizacija rekurzivnih poziva i problem ponovljenih izračunavanja

Ispod je prikazano stablo poziva funkcija za `fib(6)`:

fib(6)
├── fib(5)
│   ├── fib(4)
│   │   ├── fib(3)
│   │   │   ├── fib(2)
│   │   │   │   ├── fib(1) = 1
│   │   │   │   └── fib(0) = 0
│   │   │   └── fib(1) = 1
│   │   └── fib(2)
│   │       ├── fib(1) = 1
│   │       └── fib(0) = 0
│   └── fib(3)
│       ├── fib(2)
│       │   ├── fib(1) = 1
│       │   └── fib(0) = 0
│       └── fib(1) = 1
└── fib(4)
    ├── fib(3)
    │   ├── fib(2)
    │   │   ├── fib(1) = 1
    │   │   └── fib(0) = 0
    │   └── fib(1) = 1
    └── fib(2)
        ├── fib(1) = 1
        └── fib(0) = 0

Na osnovu ovog stabla:
- `fib(6)` poziva `fib(5)` i `fib(4)`.
- `fib(5)` poziva `fib(4)` i `fib(3)`.
- `fib(4)` poziva `fib(3)` i `fib(2)`.
- `fib(3)` poziva `fib(2)` i `fib(1)`.
- Ovaj proces se nastavlja sve dok svi pozivi ne dođu do baznih slučajeva (`fib(0)` i `fib(1)`).

Iako rekurzivni pristup jednostavno modelira Fibonačijev niz, dolazi do **ponovljenih poziva za iste vrijednosti**.

U primjeru iznad:
- `fib(4)` se poziva **tri puta** (prilikom izračuna `fib(6)`).
- `fib(3)` se poziva **pet puta**.
- `fib(2)` se poziva **osam puta**.
- `fib(1)` se poziva **trinaest puta**, što nije problem jer je bazni slučaj, ali kod složenijih problema, ovo može postati značajno.

Ovo ponavljanje čini funkciju **neefikasnom** za veće vrijednosti `n`, jer broj ponovljenih izračuna raste eksponencijalno.

:::info
### Optimizacija – Memoracija (memoization)

Iako je rekurzivna implementacija Fibonačijevog niza elegantna, uočen je jedan veliki problem – **ponavljanje istih izračunavanja**, gdje svako izračunavanje može da traje duže vrijeme. Prilikom izračunavanja `fib(6)`, funkcija se više puta koristi za izračunavanje `fib(4)` i `fib(3)`, što dovodi do nepotrebnog trošenja vremena. Na primjer, ovaj problem je posebno značajan kod računanja većih Fibonačijevih projeva, gdje bi za `fib(100)` bilo neophodno više puta izračunati `fib(98)` ili `fib(90)`, što nije brz i jednostavan zadatak.

Ovaj problem se rješava korištenjem tehnike **memoracije** (*memoization*), koja omogućava da se već izračunate vrijednosti **pamte** i **ponovno koriste**, čime se izbjegava višestruko izvršavanje istih operacija. Dakle, umjesto da se svaki put izračuna vrijednost, ona će se računati i sačuvati samo prvi put, a svaki naredni put se vrijednost samo koristi. Sličan koncept uštede može se naći kod pisanja funkcija, gdje nije neophodno svaki put pisati određene dijelove koda, nego se jednom napišu i sačuvaju kao funkcija.

Primjer optimizovane verzije funkcije prikazuje kako se rezultati izračunavanja pohranjuju koristeći **rječnik**, što je lekcija koja će biti detaljno opisana u narednim poglavljima. Za sada, dovoljno je znati da varijabla `memo` može sačuvati veći broj vrijednosti, da se svakoj od njih pristupa pomoću zagrada `[n]`, gdje je `n` ustvari vrijednost koja se traži, tj. ključ/adresa čija je vrijednost od značaja.

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0 or n == 1:
        return n
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(50))  # 12586269025

#### Kako funkcioniše ovaj pristup?
- **Memo** rječnik se koristi za pohranu ranije izračunatih Fibonačijevih brojeva.
- Prije svakog rekurzivnog poziva, provjerava se da li je vrijednost već **pohranjena** u rječniku.
- Ako se tražena vrijednost pronađe, **direktno se vraća**, bez ponovljenog računanja.
- Ako se vrijednost ne pronađe, nastavlja se rekurzija i rezultat se **dodaje u rječnik** nakon izračunavanja.

Ovaj pristup omogućava da se izračunavanje `fib(100)` **završi u milisekundama**, dok bi osnovna rekurzivna verzija zahtijevala znatno više vremena.

Tehnike poput memoracije biće dodatno razmatrane u kasnijim fazama učenja programiranja, ali je za potrebe učenja rekurzije značajno upratiti osnovni koncept ove tehnike.
:::

## Problem Hanoi kula

Problem Hanoi kula jedan je od klasičnih primjera problema koji se rješava rekurzijom. Igra se opisuje jednostavno: neka su data tri stuba (označena kao A, B i C) i `n` diskova različitih veličina. Diskovi su naslagani na stub A, pri čemu je najveći disk na dnu, a najmanji na vrhu i svaki disk je manji od svih ispod njega. Cilj je premjestiti sve diskove sa stuba A na stub C, koristeći stub B kao pomoćni, pri čemu važe sljedeća pravila:

1. Može se premjestiti samo jedan disk u jednom potezu.
2. Disk se uvijek može staviti samo na prazan stub ili na veći disk.
3. Ne smije se premjestiti veći disk na manji.

:::info
Problem Hanoi kula osmislio je 1883. godine francuski matematičar **Édouard Lucas**. Legenda kaže da su hramski svećenici u drevnom hramu radili na rješavanju ovog problema s 64 diska. Kada se svi diskovi premjeste, prema legendi, svijet će doći do kraja. U stvarnosti, čak i s idealnim uvjetima i optimalnim potezima, ovaj zadatak bi trajao milijardama godina.
:::

### Rješavanje problema
U nastavku će biti razmotrena intuitivna logika za rješavanje problema Hanoi kula, krenuvši od jednostavnih problema, prema kompleksnijim.

Ukoliko je dat jedan disk, on se jednostavno premješta sa A na C i problem je riješen. Ukoliko su data dva diska, najprije se manji disk premješta sa A na B, zatim veći sa A na C, a na kraju manji sa B na C i time je problem riješen.

Ukoliko su data tri diska, problem se može riješiti kroz niz koraka:
1. Premjestiti prva dva diska s A na B koristeći C kao pomoćni stub.
2. Premjestiti treći (najveći) disk s A na C.
3. Premjestiti dva diska s B na C koristeći A kao pomoćni stub.

Time je problem premještanja tri diska sveden na tri podproblema: premještanje dva diska sa A na B, premještanje jednog diska sa A na C i premještanje dva diska sa B na C.

Koristeći isto razmišljanje, moguće je napraviti generalizaciju rješenja.

### Generalizacija za `n` diskova

1. Premjestiti **`n-1` diskova** s A na B koristeći C kao pomoćni stub.
2. Premjestiti **najveći disk** s A na C.
3. Premjestiti **`n-1` diskova** s B na C koristeći A kao pomoćni stub.

### Rekurzivna implementacija u Pythonu
Dakle, koristeći prethodna znanja, poznato je rekurzivno rješenje problema Hanoi kula:
1. Bazni slučaj ukoliko se prebacuje jedan disk.
2. Rekurzivni slučaj prebacivanja `n` diskova pomoću dva prebacivanja `n-1` diska i prebacivanja najvećeg diska.

Implementacija problema Hanoi kula pomoću rekurzivne funkcije može izgledati kao u kodu ispod. Funkcija prihvata četiri parametra, koji se mogu posmatrati na sljedeći način:
1. Prvi parametar `n` pokazuje koliko se diskova premješta.
2. Drugi parametar `A` predstavlja kulu **sa** koje se radi prebacivanje.
3. Treći parametar `B` predstavlja **pomoću** kulu.
4. Četvrti parametar `C` predstavlja kulu na koju se radi prebacivanje.

def hanoi(n, A, B, C):
    if n == 1:
        print(f"Premjesti disk s {A} na {C}")
    else:
        hanoi(n-1, A, C, B)  # Premjesti n-1 diskova na pomoćni stub
        print(f"Premjesti disk s {A} na {C}")  # Premjesti najveći disk na cilj
        hanoi(n-1, B, A, C)  # Premjesti n-1 diskova na cilj

hanoi(3, 'A', 'B', 'C')

Izlaz funkcije za n = 3 naveden je ispod.
<pre style="background-color: #1e1e1e; color: white; padding: 20px;">
Premjesti disk s A na C
Premjesti disk s A na B
Premjesti disk s C na B
Premjesti disk s A na C
Premjesti disk s B na A
Premjesti disk s B na C
Premjesti disk s A na C
</pre>

Ukoliko je `n==1`, disk se prebacuje na željeni cilj i isposuje se prikladan tekst. Ukoliko to nije slučaj, izvode se tri koraka:
- Premještanje `n-1` diskova sa kule `A` na kulu `B` uz pomoćnu kulu `C`.
- Nakon toga, premješta se najveći disk sa kule `A` na kulu `C`.
- U posljednjem koraku, premještaju se `n-1` diska sa kule `B` na kulu `C` koristeći kulu `A` kao pomoćnu.

:::info
### Koliko je poteza potrebno za premještanje diskova?
Neka je dato `n` diskova koje treba prebaciti da bi se završila igra.

Na osnovu ranijih primjera, za jedan disk je potreban jedan potez. Za dva diska su potrebna tri poteza. Za tri diska je potrebno 7 poteza.

Matematičkom indukcijom jednostavno je pokazati da je ukupan broj poteza za prebacivanje `n` diskova dat formulom 2^`n`-1.

Stoga, u prethodnoj legendi o prebacivanju 64 diska, bilo bi potrebno najmanje 2⁶⁴ - 1 poteza. Čak i ako bi svaki potez trajao samo jednu sekundu, ukupan vremenski period potreban za završetak igre iznosio bi oko 585 milijardi godina.
:::

## Sažetak
Rekurzija omogućava funkcijama da pozivaju same sebe, čime se problemi rješavaju razlaganjem na manje podprobleme. Ključni dijelovi rekurzivne funkcije uključuju:
1. **Bazni slučaj** – Prekida dalju rekurziju kada se dostigne trivijalno rješenje.
2. **Rekurzivni slučaj** – Funkcija poziva samu sebe sa manjim problemom.
3. **Smanjenje problema** – Svaki rekurzivni poziv smanjuje složenost problema.

Jednostavni primjeri uključuju faktorijel (`n!`) i sumu prvih `n` brojeva. Funkcije bez baznog slučaja mogu dovesti do prekoračenja steka (*stack overflow*), dok višestruki pozivi, kao u Fibonačijevom nizu, mogu rezultirati ponovljenim izračunima.

Optimizacija se postiže **memoracijom** (*memoization*), gdje se ranije izračunate vrijednosti pohranjuju radi ubrzanja. Problemi poput **Hanoi kula** pokazuju kako rekurzija rješava složene zadatke elegantnim podjelama na manje korake.

Prednosti rekurzije uključuju čitljivost i prirodno rješavanje podijeli-pa-vladaj problema, dok mane uključuju veću potrošnju memorije i sporije izvršavanje u odnosu na iterativne pristupe.