Ohjelmointi 1, syksy 2024, luento19

Olin tällä sivulla luennon aikana Agorassa

Please to interact with this component.

.
Olin tällä sivulla luennon aikana Zoomissa

Please to interact with this component.

.
Olin tällä sivulla videon katsomisen aikana

Please to interact with this component.

.
Katson sivua etukäteen

Please to interact with this component.

.

# runner
# L19

19. luento: ma 4.11.2024 klo 12:15-14:00: Rekursio

Tentti ja loput demot

  • tentti, ilmoittaudu heti TIMissä
  • demo 10 ja demo 11 saa tehdä niin monta tehtävää kuin haluaa (ei 8 ylärajaa)
  • erityisesti piirtotehtävä (tai tehtäviä) tulee tenttiin, eli harjoitelkaa demo 10:ssä. Varmaan lisätään esimerkki myös demo 11.
  • demo 11 on mallitentti, tentissä osattava myös itse tehdä testejä
# GLO_DemoN2

Kertausta

TDD:

Sijoituksen suunta

# sijoitusblle

Kasvatusoperaattorit

# muuttujat1
# muuttujat2
# muuttujat3

Kysymyksiä

Rekursio

  • rekursio = katso rekursio


Kurssin aikana sinun on tarkoitus oppia seuraavia asioita (osaamisen taso sovelletulla Bloomin asteikolla: 1=muistaa, 2=ymmärtää, 3=osaa soveltaa, 4=osaa analysoida, 5=osaa arvioida, 6=osaa luoda)

Siirrä alla osaamisesi (punainen pallukka) aina sitä vastaavalle kohdalle. Keltainen ruutu on tavoite johon tulisi päästä kurssin lopuksi. Ruksaa ensin muokkaa.

# goaltable2

Please to interact with this component.

Osattava asia123456
Rakenteisen ohjelmoinnin perusajatus o
Algoritminen ajattelu o
C#-kielen perusteet o
Peräkkäisyys o
Muuttujat o
Aliohjelmat ja funktiot o
Parametrin välitys o
Ehtolauseet o
Silmukat o
Taulukot o
Tiedostot ohjelmasta käytettynä o
Olioiden käyttö o
Yksikkötestit (TDD) o
Debuggerin käyttö o
Lukujärjestelmät, ASCII-koodi o
Rekursio o
Dokumentointi ja sen lukeminen o

Rekursiolla tarkoitetaan algoritmia, joka tarvitsee itseään ratkaistakseen ongelman.

  • hakemistopuu
# binaaripuu
# shell1
# hanoijs
# pyhanoi
  • Fibonacin jono

    tai iteratiivisesti silmukalla tai suoraan analyyttisessä muodossa

    public static void Rekursio(parametrit) 
    {
        if (lopetusehto) return;
        // toimenpiteitä ... 
        Rekursio(uudet parametrit);  // Itsensä kutsuminen
        // mahdollisesti lisää lauseita
    }

Kertoma

Kertomaa ei ole järkeä laskea rekursiolla, mutta koska sille on yksinkertainen rekursiivinen määritelmä, niin se usein esitetään ensimmäisenä ohjelmallisena rekursioesimerkkinä.

# rek
# kertoma
Kuva 30: Kertoman laskeminen rekursiivisesti. Vaiheet numeroitu.
Kuva 30: Kertoman laskeminen rekursiivisesti. Vaiheet numeroitu.
# ae_rekursioCS
  • katso myös debuggerilla
# binomi

Tämän voi ajatella myös niin, että 5 alkiota voidaan laittaa 5! eri järjestykseen. Kun niistä otetaan 2 ensimmäistä, niin laskussa 5! tuli laskettu liikaa kaikki näiden kahden erilaiset järjestykset. Toisaalta kussakin eri 5! järjestyksessä kahden alkion valinnan kannalta samoja ovat järjestykset, joissa jäljelle jääneet 3 ovat eri järjestyksissä.

# kolmioluku

Kolmioluku

# kolmioluku21
# nelioluku

Neliöluku

# neliolukutex
# neliolukufor

Mielenkiintoista sinällään, mutta neliöluvun voi esittää myös kolmiolukujen avulla:

Voit halutessasi kokeille tehdä tätäkin ohjelmaksi sekä rekursiolla että ilman.

Fraktaalit

Madelbrotin joukko
Madelbrotin joukko

Kochin lumihiutale

Sierpinskin kolmio

# k33

Kuva 33: Kolmion pisteiden laskeminen.

# k32_1
# k32_2
# Plugin1
# muitakielia

Rekursio muilla ohjelmointikielillä

Haskell:

sum []   = 0
sum (x:xs) = x + sum xs
# scheme_fac_slow

Esimerkkien define/contract ei ole pakollinen, mutta toimii apuna eräänlaiselle tyyppijärjestelmälle ja tuottaa virheiden sattuessa parempia viestejä käyttäjälle.

4 days ago
# scheme_fac_fast
# scheme_sum
# hellofs
# listfs
# listfs2

Fibonaccin luku

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.