DATS 2300202005

Prev Up Next

Introduksjon til rekursjon

I denne videoen gir vi en kort introduksjon til rekursive funksjoner - hva stack overflow er - og hva slags krav vi stiller til en rekursiv funksjon for at den skal fungere som tiltenkt.

Rekursiv n! (n fakultet)

I denne videoen går vi gjennom hvordan vi kan regne ut n! rekursivt. I en for-løkke kan vi enkelt regne det ut som følger:

int n_fakultet=1;
for (int i=2; i    n_fakultet = n_fakultet*n;
}

Dette gir da f.eks 5! = 1*2*3*4*5=120, og er utregnet på en tradisjonell iterativ måte. I videoen går vi gjennom hvordan vi kan regne ut dette ved å bruke rekursjon isteden. 

 

Rekursivt binærsøk

I denne videoen går vi gjennom hvordan vi kan søke etter ett tall ved hjelp av et binært rekursivt søk i en sortert liste. 

Rekursive permutasjoner

I denne videoen går vi gjennom hvordan vi kan generere permutasjoner ved hjelp av en rekursiv funksjon. Hele essensen er at vi tar inn en tallrekke, f.eks 1, 2, 3. Så  ser vi på hvordan vi kan systematisk permutere denne tallrekkefølgen. 

Flerdimensjonelle tabeller og Hanois tårn

I disse to videoene  går vi gjennom hvordan et array er lagret på datamaskinen - og repeterer minneaddresser, cache hierarki, og hvorfor quicksort passer veldig bra på maskiner med cache. Videre går vi gjennom Hanois tårn som en rekursiv metode.