Hogyan lehet az első N darab páratlan szám összegét rekurzívan kiszámolni?

Pseudo kódban:

func firstNOddSum(n, sum): if n==1 return sum+1 else return firstNOddSum(n-2,sum+n)

Különben honnan tudná, hogy hol jár és mikor kell megállni?

Ha csak egy sum-ot adsz át és kap a függvény egy 9-et, honnan tudod, hogy most 9-ről indultunk és 7-nél kell folytatni, vagy 5-ről indultunk és meg kell állni?

Kiinduló szabály: Első 0 db páratlan szám összege: 0

Indukciós lépés: Ha ismerjük az első n db páratlan szám összegét, abból megkaphatjuk az első n + 1 db páratlan szám összegét, csak adjuk hozzá még az n + 1-edik páratlan számot

Egyszerűsödik a formalizmus, ha 0-alapú indexelést használunk, ekkor a szabályok igy fognak kinézni:

Kiinduló szabály: Első 0 db páratlan szám összege: 0 (ez változatlan)

Indukciós lépés: Ha ismerjük az első n db páratlan szám összegét, abból megkaphatjuk az első n + 1 db páratlan szám összegét, csak adjuk hozzá még az n-edik páratlan számot (0-alapú indexelésben értve)

0 alapú indexelésnél a 0-ik páratlan szám az 1, az 1-edik páratlan szám a 3, szóval az k-adik páratlan szám a 2k+1

Ezak alapján már egész konrétan felírhtó a rekurzió:

Kiinduló szabály: Első 0 db páratlan szám összege: 0

Indukciós lépés: Ha ismerjük az első n db páratlan szám összegét, abból megkaphatjuk az első n + 1 db páratlan szám összegét, csak adjuk hozzá még magát a 2n + 1 számot.

Szóval:

P(0) = 0

P(n + 1) = P(n) + 2n+1

E alapján már simán egy Haskell programmal is lehet ellenőrizni:

your-prompt$ ghci -XNPlusKPatterns

GHCi, version 8.6.5: [link] :? for help

Loaded package environment from /home/physis/Documents/my-upwork/hpr/gitlab/assignment2/.ghc.environment.x86_64-linux-8.6.5

Prelude> let {p 0 = 0; p(n+1) = p n + 2*n+1}

Prelude> p 0

0

Prelude> p 1

1

Prelude> p 2

4

Prelude> p 3

9

Prelude> p 4

16

Prelude> p 5

25

Prelude> :q

Leaving GHCi.

your-prompt$