#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/recursion-fundamentals/power-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/recursion-fundamentals/power-implementation

Repovive

Power Function - Implementation - Recursion Fundamentals | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units

Open in Course

Power Function - Implementation

The efficient code

Here is the faster recursive power function:

function power(x, n)
    if n = 0 then
        return 1
    if n is even then
        half := power(x, n / 2)
        return half × half
    return x × power(x, n - 1)

If $n$ is $0$ , return $1$ . If $n$ is even, compute power(x, n / 2) once, store it, and square it. If $n$ is odd, multiply $x$ by power(x, n - 1). Trace power(2, 10): you get power(2, 5) squared. Then power(2, 5) = $2$ × power(2, 4). Then power(2, 4) = power(2, 2) squared. Then power(2, 2) = power(2, 1) squared. Then power(2, 1) = $2$ × power(2, 0) = $2$ . Just $6$ calls for $n = 10$ .

Time complexity: $O(\log n)$ .

Space complexity: $O(\log n)$ due to the recursive call stack.

HannahHi! I'm Hannah. Let me know if you need help understanding anything!