The referenced paragraph does not exist.

Ohjelmointi 1, syksy 2017, luento 19

# L19

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

Versionhallinnassa

- lähtötilanne: svn export https://svn.cc.jyu.fi/srv/svn/ohj1/esimerkit/2017s/luennot/live19
- lopputilanne: svn export https://svn.cc.jyu.fi/srv/svn/ohj1/esimerkit/2017s/luennot/luento19

Kertausta

Kasvatusoperaattorit

# muuttujat1 
        int i = 3;
        int a = i++;
        Console.WriteLine($"a = {a}, i = {i}");

 
# muuttujat2 
        int i = 3;
        int a = ++i;
        Console.WriteLine($"a = {a}, i = {i}");

 
# muuttujat3 
        int i = 3;
        int a = 0;

        a = i+1;
        Console.WriteLine($"a = {a}, i = {i}");

 

Kysymyksiä

Rekursio

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

  • hakemistopuu
# shell 
ls -R /cs | grep ^/

 

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

Kertoma

# rek

Kirjoita tähän miten rekursio toimii

4! = ???

 
# kertoma 
//
    /// <example>
    /// <pre name="test">
    ///   Kertoma(0) === 1L;
    ///   Kertoma(1) === 1L;
    ///   Kertoma(2) === 2L;
    ///   Kertoma(5) === 120L;
    ///   Kertoma(6) === 720L;
    /// </pre>
    /// </example>
    public static long Kertoma(long n)
    {
        return 1;
    }

    /// <example>
    /// <pre name="test">
    ///   KertomaFor(0) === 1L;
    ///   KertomaFor(1) === 1L;
    ///   KertomaFor(2) === 2L;
    ///   KertomaFor(5) === 120L;
    ///   KertomaFor(6) === 720L;
    /// </pre>
    /// </example>
    public static long KertomaFor(long n)
    {
        return 1;
    }

 
Kuva 30: Kertoman laskeminen rekursiivisesti. Vaiheet numeroitu.
Kuva 30: Kertoman laskeminen rekursiivisesti. Vaiheet numeroitu.
# ae_rekursioCS

Animaatio: Suorita animaatio rekursiosta

Askella rekursiota vihreällä nuolella. Tutki kertomaa
  • katso myös debuggerilla
# binomi

Binomikerroin

Monellako tavalla voidaan valita 2 alkiota 5:stä?

a b c d e

a b
a c
... täydennä **

 

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ä.

\[\binom {5}{2} = \frac {5!}{2! * (5-2)!} = \frac{1*2*3*4*5}{ 1*2 * 1*2*3} = \frac{4*5}{1*2} = 10\]

Fraktaalit

Madelbrotin joukko
Madelbrotin joukko

Kochin lumihiutale

Sierpinskin kolmio

# k33

Kuva 33: Kolmion pisteiden laskeminen.
# k32_1
# k32_2
# Plugin1 
//
    private const double pieninKorkeus = 1;

    /// <summary>
    /// Piirtää Sierpinskin kolmion.
    /// </summary>
    /// <param name="canvas">Piirtoalusta</param>
    /// <param name="x">Alareunan x</param>
    /// <param name="y">Alareunan y</param>
    /// <param name="h">Korkeus</param>
    public static void SierpinskinKolmio(Canvas canvas, double x, double y, double h)
    {
        if (h < pieninKorkeus) return; // ÄLÄ VAAN POISTA TÄTÄ ja muu jälkeen

    }

 

Rekursio muilla ohjelmointikielillä

Haskell:

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

F# kertoma

let rec kertoma n: bigint =
    match n with
        | 0 | 1 -> bigint 1
        | _ -> bigint n  * kertoma(n-1)

printfn "%A" (kertoma 52)

 
# listfs

F# summa

let rec summa lista =
    match lista with
        | [] -> 0
        | head :: tail -> head + summa tail

let lista = [ 63; 25; 27 ]
printfn "%d" (summa lista)

 
# listfs2

F# summa, häntärekursio, eli ei vie pinoa

let summa lista =

    let rec summa lista accum =

        match lista with
            | [] -> accum
            | head :: tail -> summa tail (accum + head)
    summa lista 0

printfn "%d" (summa [ 63; 25; 27 ] )

 

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