Cad is Athfhillteachas?

Question

Accepted Answer

**Athfhillteachas** a tharlú nuair a ghlaoch feidhm ar í féin chun leagan níos lú den fhadhb chéanna a réiteach. Tá gach athfhillteachas i bhfeidhm go bhfuil **cás bunúsach** ag teastáil a stopann é agus **cás athfhillteach** a ghluaiseann i dtreo an chása bhunúsaigh.

## An smaoineamh

Bris an fhadhb ina bhfo-fhadhbanna comhionanna níos lú. Brúnn gach glaoch fráma ar an **chruach glaoch**; baintear iad ar ais trí thúchanna.

## Sampla

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Rian

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Castacht

Anseo **O(n)** in am agus **O(n)** spáis an chruaich (fráma amháin in aghaidh an glaoch).

## Doilbhéasa

- **Cás bunúsach ar iarraidh** -> athfhillteachas gan deireadh -> foluain an chruaich.
- Féadfaidh athfhillteachas domhain an chruach a thrabhairt; níl barrfhéachaint ar ghlaochanna deireannacha ag roinnt teangacha.
- Ath-ríomh ar fho-fhadhbanna a fhorluíonn féadann sé a phléascadh go ham easpóiméadúil (a shocrú le cuimhneachán).

## Cén fáth a bhfuil sé tábhachtach

Cuireann athfhillteachas in iúl go nádúrtha fadhbanna féin-bhhunus — crainn, ghraif, roinnt agus conquer — i bhfad níos geal ná lúb.

Sé an múnla meabhrach taobh thiar de shórtáil fhusion, backtracking, agus clár dinimiciúil.

Tuigbheáil ar an chruach glaoch a dhéanann tú níos fearr freisin ag dífhostú agus ag smaoineamh ar an chuimhne.