Számoljuk ki egy szám hatványát!

Bár a JavaScriptben létezik a pow beépített függvény számok hatványának kiszámítására, azért te is megírhatod a saját rekurzív függvényedet, ami nagyon hatékony lehet. Az egyetlen kikötés az, hogy a kitevőnek egész számnak kell lennie.

Tegyük fel, hogy ki szeretnéd számítani $x^n$‍ értékét, ahol $x$‍ egy tetszőleges valós szám, $n$‍ pedig egy tetszőleges egész. Egyszerű a dolgunk, ha $n$‍ 0, mivel $x^0=1$‍ függetlenül $x$‍ értékétől. Ez egy jó alapeset lesz.

Most vizsgáljuk meg, mi van abban az esetben, ha $n$‍ pozitív. Kezdjük azzal, hogy felidézzük: akkor, amikor $x$‍ hatványait összeszorozzuk, akkor a kitevőket összeadjuk: $x^a\cdot x^b=x^{a+b}$‍ tetszőleges $x$‍ és bármilyen $a$‍ és $b$‍ kitevők esetén. Ezért, ha $n$‍ pozitív és páros, akkor $x^n=x^{n/2}\cdot x^{n/2}$‍. Ha $y=x^{n/2}$‍ értékét rekurzívan szeretnéd kiszámítani, akkor $x^n$‍-t kiszámíthatod $y\cdot y$‍ alakban. Mi van akkor, ha $n$‍ pozitív és páratlan? Akkor $x^n=x^{n-1}\cdot x$‍, és $n-1$‍ vagy 0, vagy pozitív és páros. Az előbb viszont láttuk, hogyan kell kiszámítani $x$‍ hatványát abban az esetben, ha a hatvány 0, vagy pozitív és páros. Ezért ki tudod számítani $x^{n-1}$‍ értékét rekurzívan, majd az eredményt felhasználva kiszámítod $x^n=x^{n-1}\cdot x$‍ értékét.

Mi van akkor, ha $n$‍ negatív? Akkor $x^n=1/x^{-n}$‍, ahol a $-n$‍ kitevő pozitív, hiszen az egy negatív szám ellentéte. Ezután rekurzívan kiszámítod $x^{-n}$‍ értékét, és veszed a reciprokát.

A fenti megállapításokat összegezve, az alábbi rekurzív algoritmust fogalmazhatjuk meg $x^n$‍ kiszámításához:

Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.