過去ログをよく読みましたか？
その式は間違っています。正しくは、

g(x,y) = 1                     (y = 0 のとき)
g(x,y) = g(x*x, y/2)           (y が偶数のとき)
g(x,y) = x * g(x*x, (y-1)/2)   (y が奇数のとき)

意味は、具体例を考えれば分かるでしょう。

x の 0乗は、1。       (y = 0 のとき)

g(x,6) = g(x*x,3)     (y が偶数のとき)
すなわち、x * x * x * x * x * x = (x*x) * (x*x) * (x*x)

g(x,7) = x * g(x*x,3) (y が奇数のとき)
すなわち、x * x * x * x * x * x * x = x * ((x*x) * (x*x) * (x*x))

この説明で納得できますか。

x の 6乗を求めるのに掛け算を 5回しないといけないが、
g(x,6) = g(x*x,3) で、掛け算が 3回で済みますよ、ということです。

> g(x,y) = 1                     (y = 0 のとき)
> g(x,y) = g(x*x, y/2)           (y が偶数のとき)
> g(x,y) = x * g(x*x, (y-1)/2)   (y が奇数のとき)

この式で再帰関数を作ると、
 
g(x,6) = g(x*x,3) 
       = (x*x) * g((x*x)*(x*x), 1)
       = (x*x) * ((x*x)*(x*x)) * g(((x*x)*(x*x))*((x*x)*(x*x)), 0)  ...(A)
       = (x*x) * ((x*x)*(x*x)) * 1
       = (x*x) * ((x*x)*(x*x))                                      ...(B)

(A)から(B)への推移を工夫しないと y=6 程度では掛け算の回数は増えてしまいますね。
もっと大きい y については確実に減るのでしょうが。

    g(x,y) = x  (y = 1 のとき)