PR2ET11: Pinu ja rekursioon

Labori materjal

Slaidid: Rekursioon
Slaidid: Pinu (magasin)
Tunnis läbi tehtavad näited
- Rekursiivne faktoriaal: https://blue.pri.ee/ttu/files/iax0584/demokood/factorial.c
- Sabarekursiivne faktoriaal: https://blue.pri.ee/ttu/files/iax0584/demokood/factorial_tail.c
- Pinu: https://blue.pri.ee/ttu/files/iax0584/demokood/stack_base.c
Alternatiivne näide: Pinu, mis kasutab pinuviita (SP) viidana: https://blue.pri.ee/ttu/files/iax0584/demokood/stack_sp_as_pointer.c

Laboriülesanded

Selles laboris on kaks baasülesannet, üks iseseisev edasijõudnute ülesanne rekursioonile ning üks edasijõudnute laiendusülesanne pinule.

Ülesanne 1: Rekursiooni ülesannete komplekt

Esimese ülesande raames tuleb sul luua kolm rekursiivset programmi (osa 1, 2 ja 3). Ülesanne saab esitada ainult siis, kui kõik kolm on valmis!

NB! Tegu on äärmiselt lihtsate ülesannetega, väldi internetist lahenduste otsimist!

Tunni alguses luuakse näidislahendus faktoriaali rekursiivsest lahendamisest!

Nõuded

Võid laheduse luua ühe failina kus on kolm rekursiooni korraga või kolme erineva programmina. Näited on tehtud kolme erineva rakendusena.
Kõigil juhtudel on kohustuslik toetada sisendina positiivset täisarvu. Negatiivse sisendi korral on kas lahenduses märgitud eraldi vastus (baasjuht) või tuleb kuvada viga.
Sisendi võid küsida rakenduse sees või lugeda käsurea argumendina.
Iteratiivseid lahendusi kasutada ei tohi, kõik kolm osa peavad olema lahendatud rekursiivselt.
Esitada saab ülesannet vaid siis, kui kõik kolm osa on valmis.

Osa 1: summa

Loo rakendus, mis leiab kõigi positiivsete täisarvude summa kuni kasutaja sisestatud arvuni. Negatiivse argumendi korral rekursiivsele summa funktsioonile on summa 0 (positiivsed arvud puuduvad, baasjuht).

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 0
sum(0) = 0
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 1
sum(1) = 1
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 2
sum(2) = 3
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 3
sum(3) = 6
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum -1
sum(-1) = 0

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 0

sum(0) = 0

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 1

sum(1) = 1

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 2

sum(2) = 3

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum 3

sum(3) = 6

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./sum -1

sum(-1) = 0

Osa 2: astendamine

Loo rakendus, mis lubab astendada x^y. math.h teegi ja sisse ehitatud astmefunktsioonide kasutamine ei ole lubatud.

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 8
2^8 = 256
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 5 3
5^3 = 125
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 5 0
5^0 = 1

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 8

2^8 = 256

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 5 3

5^3 = 125

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 5 0

5^0 = 1

NB! Kuigi nõue on vaid rakendus luua positiivsetele täisarvudele, siis võid proovida ka laiendada lahendust näiteks negatiivsetele arvudele.

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow -5 2
-5^2 = 25
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow -5 3
-5^3 = -125
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -1
2^-1 = 0.5000
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -2
2^-2 = 0.2500
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -3
2^-3 = 0.1250

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow -5 2

-5^2 = 25

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow -5 3

-5^3 = -125

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -1

2^-1 = 0.5000

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -2

2^-2 = 0.2500

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./pow 2 -3

2^-3 = 0.1250

Osa 3: Fibonacci arvud.

Loo rakendus, mis leiab soovitud Fibonacci arvu. n-indaks fibonacci arvuks on selle kahe eelneva Fibonacci arvu summa ehk siis fib_x = fib_{x – 1} + fib_{x – 2}. Erinevalt eelnevatest rekursioonidest on Fibonacci jadal kaks seetõttu ka 2 baasjuhtu.

Fibonacci arvud on 0, 1, 1, 2, 3, 5, 8, 13, 21, …,

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib -1
Error! Input must be 0 or greater!
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 0
fib(0) = 0
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 1
fib(1) = 1
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 6
fib(6) = 8
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 7
fib(7) = 13
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 45
fib(45) = 1134903170

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib -1

Error! Input must be 0 or greater!

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 0

fib(0) = 0

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 1

fib(1) = 1

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 6

fib(6) = 8

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 7

fib(7) = 13

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib 45

fib(45) = 1134903170

Märkasid kui kaua aega läks viimase leidmiseks? See on ootuspärane laboriülesande lahendamisel ning parandada vaja ei ole, kuid mõtle kindlasti miks nii juhtus!

Kõik 3 valmis, näita nüüd ülesanne ette!

Programmi ajakulu saad mõõta kasutades time programmi. Siin on võrdluseks kaks erinevat rekursiivset lahendust samast programmist. Teisel juhul on kasutatud lähenemist mida kutsutakse tail-recursion’iks ehk sabarekursiooniks. Selle kohta võid vajadusel uurida omal käel.

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$  time ./fib 45
fib(45) = 1134903170

real    0m8,520s
user    0m8,518s
sys     0m0,000s
risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$  ./fib_tail 45
fib(45) = 1134903170

real    0m0,001s
user    0m0,000s
sys     0m0,001s

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ time ./fib 45

fib(45) = 1134903170

real 0m8,520s

user 0m8,518s

sys 0m0,000s

risto@risto-tux:~/Nextcloud/prog2/wk10_recursion_stack$ ./fib_tail 45

fib(45) = 1134903170

real 0m0,001s

user 0m0,000s

sys 0m0,001s

Ülesanne 2: pinu

Selles ülesandes loome menüüprogrammi, mille sisuks on demonstreerida pinu funktsioone. Tunnis lahendatav ülesanne on demonstratiivne ning toetab varasemalt õpitud dünaamilist mälu – selline lahendus ei too oma keerukuse tõttu välja pinu eeliseid kiiruses!

Tunni alguses luuakse osaline näidis, kus lahendame ära Push() funktsiooni!

Nõuded

Loo oma rakendusele menüü struktuur – kasutaja peab saama valida millist operatsiooni teostada
Loo Pop() ja Peek() funktsioonid
- Pop() eemaldab pealmise elemendi pinust ja tagastab selle väärtuse.
- Peek() tagastab pealmise elemendi, kuid ei eemalda seda
Loodavad funktsioonid ise elementide väärtusi kuvada ei tohi! Ekraanile kuvatakse väärtused pärast menüüsse tagastamist!
NB! Baasversioonis on lubatud reserveerida üks väärtust tähistamaks pinu alatäitumist, et väljastuses illegaalset väärtust ei kuvataks. Edasijõudnute versioonis see lubatud ei ole.
Vastavalt funktsioonile veendu, peavad olema realiseeritud kas ala- või ületäitumise kontrollid.
Pööra tähelepanu olukorrale kus pinust eemaldatakse kõik elemendid – reallociga 0 baiti küsida on ohtlik, tuleks kasutada free funktsiooni!

Pinu silumisfunktsioon

Selleks, et saaksid paremat aimu pinu sisust pakun sulle ka silumisfunktsiooni. Tegelikus olukorras sellist funktsiooni sageli rakendada ei saaks kuna see võib olla vastuolus pinu piirangute ning ka konkreetse pinu realisatsiooniga!.

void debug_stack(stack st)
{
    printf("DEBUG\n");
    printf("\tStack size: %d\n", st.size);
    printf("\tData pointer: %p\n", st.data);
    
    if (st.size != 0 && st.data == NULL)
    {
        printf("Sanity check failed!\n");
        printf("Stack is NULL, but size is not 0\n");
        return;
    }
    
    if (st.size == 0 && st.data != NULL)
    {
        printf("Sanity check failed!\n");
        printf("Stack data is not NULL, but size is 0\n");
        return;
    }
    
    printf("\tValues: ");
    for (int i = st.size - 1; i >= 0; i--)
    {
        printf("%d ", st.data[i]);
    }
    printf("\n\n");
}

void debug_stack(stack st)

{

printf("DEBUG\n");

printf("\tStack size: %d\n", st.size);

printf("\tData pointer: %p\n", st.data);

if (st.size != 0 && st.data == NULL)

{

printf("Sanity check failed!\n");

printf("Stack is NULL, but size is not 0\n");

return;

}

if (st.size == 0 && st.data != NULL)

{

printf("Sanity check failed!\n");

printf("Stack data is not NULL, but size is 0\n");

return;

}

printf("\tValues: ");

for (int i = st.size - 1; i >= 0; i--)

{

printf("%d ", st.data[i]);

}

printf("\n\n");

}

Testimine

Testimisel pööra tähelepanu järgnevale:

pinu ületäitumine
pinu alatäitumine
pinu andmete vabastamine pärast viimase elemendi kustutamist (valgrind!)
Mälulekke ohule kui programm suletakse kui pinus on veel andmeid (valgrind!)

Ava mind väljundi nägemiseks

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution 
Maximum stack size is limited to 3!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 0
        Data pointer: (nil)
        Values: 

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 97

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 1
        Data pointer: 0x558cd0c07ac0
        Values: 97 

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 34

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 25

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 99
ERROR: Stack overflow!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 3
        Data pointer: 0x558cd0c07ac0
        Values: 25 34 97 

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
Got 25

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
Got 34

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
Got 97

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
ERROR: Stack underflow!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 0
        Data pointer: (nil)
        Values: 


1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 0

100

101

102

103

104

105

106

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution

Maximum stack size is limited to 3!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 0

Data pointer: (nil)

Values:

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 97

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 1

Data pointer: 0x558cd0c07ac0

Values: 97

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 34

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 25

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 99

ERROR: Stack overflow!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 3

Data pointer: 0x558cd0c07ac0

Values: 25 34 97

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

Got 25

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

Got 34

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

Got 97

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

ERROR: Stack underflow!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 0

Data pointer: (nil)

Values:

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 0

Edasijõudnute ülesanne 1: rekursiooni praktiline kasutusjuht

See edasijõudnute ülesanne on sulle antud ingliskeelse algoritmi kirjeldusena. Tegu on täiesti eraldiseisva ülesandega, mis ei ole seotud eelnevalt tehtud tunnitöö lahendusega!

NB! Olulised muutujad on antud matemaatikutele omases kirjapildis ehk üksikute tähtedena – soovitus oma programmis kasuta pikemaid ja selgitavamaid nimesid nagu on programmeerimises omane.

Given search key K and an array A of n integers A₀, A₁, … , A_{n – 1} sorted such that A₀ ≤ A₁≤ … ≤ A_{n – 1} use the following algorithm to find if K ∈ A

Set lowIndex L to and highIndex H to n − 1 .
Call the recursive function using 4 arguments – A, L, H, K .
- If L > H , the search terminates as unsuccessful – return 0
- Set m (the position of the middle element) to the floor of (L + H) / 2
- If A_m < K, set L to m + 1 , call recursion again
- If A_m > K, set H to m − 1 , call recursion again
- If A_m = K, the search was successful – return 1

Ülesanne valmis, valmista enne esitamist ette vastused järgmistele küsimustele. Kui vastused olemas, anna märku!

Ajalike keerukus – võrdle antud algoritmi ja tavalist lineaarset otsingut. Mitu võrdlust läheks vaja, et võrrelda massiivi kus on
- 16 liiget
- 256 liiget
- 100 000 liiget
Anna hinnang algoritmi keerukusele – nt konstantne, logaritmiline, lineaarne, eksponentsiaalne (https://www.bigocheatsheet.com)
Kui massiiv poleks sorteeritud, kas see algoritm töötaks?

Edasijõudnute ülesanne 2: pinu laiendus

Selles ülesandes loome paar lisavõimalust oma pinule ning teeme seda veidi universaalsemaks.

Nõuded

Lisa oma pinule järgmised funktsioonid
- Duplicate()
- Swap()
Need funktsioonid tohivad kasutada ainult Push() ja Pop() funktsioonide väljakutseid!
Muuda oma Pop() ja Peek() funktsioonide kujusid sedasi, et kehtiksid järgmised nõuded
- Pinu peab toetama kõiki arve (ei tohi olla reserveeritud mitmetähenduslike väärtusi).
- Juhul kui tekib pinu alatäitumine, siis kuvatakse vaid veateade, väärtust ennast ei kuvata
Märkus: Lisafunktsioonide jaoks pead suure tõenäousega muutma ka Push() funktsiooni!

Testimine

Olulised kitsaskohad mida testida (lisaks tavaolukordadele)

Pop(), kui pinu on tühi (ei tohi numbrit väljastada

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution 
Maximum stack size is limited to 3!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 2
ERROR: Stack underflow!

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution

Maximum stack size is limited to 3!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 2

ERROR: Stack underflow!

Duplicate(), kui andmeid pinus pole
Duplicate(), kui pinu on täis

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution 
Maximum stack size is limited to 3!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 5
ERROR: Stack underflow!
ERROR: Cannot duplicate!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 25

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 5

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 5

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 5
ERROR: Stack overflow!
ERROR: Cannot duplicate!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 3
        Data pointer: 0x561f250ebac0
        Values: 25 25 25

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution

Maximum stack size is limited to 3!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 5

ERROR: Stack underflow!

ERROR: Cannot duplicate!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 25

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 5

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 5

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 5

ERROR: Stack overflow!

ERROR: Cannot duplicate!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 3

Data pointer: 0x561f250ebac0

Values: 25 25 25

Swap(), kui pinus andmeid pole
Swap(), kui pinus on vaid 1 liige

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution 
Maximum stack size is limited to 3!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 4 
ERROR: Stack underflow!
ERROR: Cannot swap!

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 1
Enter value: 2

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 4
ERROR: Stack underflow!
ERROR: Cannot swap !
Original state restored.

1 - Push        4 - Swap
2 - Pop         5 - Duplicate
3 - Peek        9 - DEBUG
0 - exit
> 9
DEBUG
        Stack size: 1
        Data pointer: 0x55e8aa1e6ac0
        Values: 2

risto@risto-wk:~/Nextcloud/prog2/wk10_recursion_stack$ ./stack_solution

Maximum stack size is limited to 3!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 4

ERROR: Stack underflow!

ERROR: Cannot swap!

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 1

Enter value: 2

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 4

ERROR: Stack underflow!

ERROR: Cannot swap !

Original state restored.

1 - Push 4 - Swap

2 - Pop 5 - Duplicate

3 - Peek 9 - DEBUG

0 - exit

> 9

DEBUG

Stack size: 1

Data pointer: 0x55e8aa1e6ac0

Values: 2

Pärast seda tundi peaksid

Teadma mida tähendab rekursioon, sh rekursiivne funktsioon ja rekursiivne andmetüüp.
Oskama kirjutada lihtsaid rekursioone
Teadma, et eksisteerib ka sabaga rekursioon
Teadma rekursioonide headest omadustest ja probleemidest
Teadma rekursioonide kasutusvaldkondi
Teadma mida tähendab abstraktne andmestruktuur
Teadma mis on pinu ning millised on selle omadused
Teadma pinu kasutusvaldkondi
Oskama luua pinu ning sellele kohustuslike funktsioone

Täiendav materjal

Introduction to Recursion – Data Structure and Algorithm Tutorials
https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/
Merge sort (recursion)
https://www.geeksforgeeks.org/merge-sort/
Quick sort (recursion)
https://www.geeksforgeeks.org/quick-sort/
Stack data structure
https://en.wikipedia.org/wiki/Stack_(abstract_data_type)