Golangの以下のコードにおいて、再帰関数のほうが単純なFor文より早い理由

Question

前提

比較する2つの関数はmainに定義されているsolveとsolve2です。また、solveは関数内でdivideByTwoを参照しています。
実行時間の計測にはtime.Nowを用いました。
テストケースは乱数を用いて作成しています。

自分なりの推測

最初は再帰関数のほうが、関数参照の分遅くなると考えていましたが、実際には違いました。
2つの計算量が異なっている場合は教えてください。（計算量の違いはパット見ではわかりませんでした。）

これは計算量が同じである場合の推測ですが、solve2関数内のifにおいて、毎回int(math.Pow(2, float64(k))という型変換とべき乗計算を行っているのが実行時間が遅い要因担っているのかもしれません。

しかし、それにしても2つのケースで決定的に実行速度が違うので、どこかで計算量の差異があるのではと考えています。

実行結果

200
9099523047102087168 8881098465174618112 2080663027845169152 4571153621781053440 2344123606046343168 1485061977125421056 4983232987685453824 2860911663287107584 514536257427079168 3716595592487501824 782500435255623680 -8863084066665136128 9190720939556339712 5730830525828956160 5324380659458768896 3687322194909593600 1364590687093260288 1628051265294434304 3645663898356416512 -8193173622093774848 558446353793941504 6155294790708625408 1721500957562372096 7047007516927983616 9061242450269437952 -7246291800439128064 -9115285645797883904 3252724830868340736 3142386639997763584 3395714119037353984 6239737283721822208 460493061898633216 8318148511753306112 7692148163548807168 6113636494155448320 6031445800955936768 1956814038092480512 711568741124538368 1673087261568139264 5659898831697870848 7221522002488590336 3480156612050550784 5849050016047431680 635007547459239936 2740440373254946816 4670232813583204352 4592545720011063296 4869517097094348800 6935543426150563840 1524468473864912896 2204512017597857792 4190599453268246528 8095220330198466560 2476979795053772800 3378825620434714624 -8644659484737667072 3252724830868340736 5110459677158670336 -7521011377708728320 -7912824545289961472 2760706571578114048 -8864209966571978752 2934095157231878144 176766285374291968 -9138929543841579008 -7380273889353400320 6262255281858674688 8109857028987420672 5386305154335113216 6470546764624560128 1760907454301863936 4928063892250165248 -8310267212405407744 -7504122879106088960 6133902692478615552 5736460025363169280 1776670052997660672 8403716904673345536 9003821555020464128 7229403301836488704 -8736983277098762240 1074108511127863296 1281274093986906112 3528570308044783616 -8041177134670020608 67553994410557440 3415980317360521216 -8714465278961909760 4382002437431492608 2255177513405775872 -8449878800853893120 -7934216643519971328 2867667062728163328 -8192047722186932224 8940771160237277184 7322852994104426496 622622648483971072 -7363385390750760960 2483735194494828544 1800313951041355776 8360932708213325824 1522216674051227648 1706864258773417984 -7460212782739226624 4152318856435597312 9019584153716260864 3840444582240190464 5951506907570110464 -8774137974024568832 4090394361559252992 3489163811305291776 -8815796270577745920 -8773012074117726208 -8783145173279309824 6062970998347530240 1461418079081725952 -8011903737092112384 6910773628200026112 -8007400137464741888 6637179950837268480 8699828580172955648 6533597159407747072 4483333429047328768 2341871806232657920 2327235107443703808 1431018781596975104 556194553980256256 3475653012423180288 -7390406988514983936 -8333911110449102848 6815072136118403072 8079457731502669824 5501146944833060864 6430014367978225664 1562749070697562112 4222124650659840000 1721500957562372096 3173911837389357056 4937071091504906240 8899112863684100096 1379227385882214400 5120592776320253952 4067876363422400512 1726004557189742592 4072379963049771008 8827055269646172160 609111849601859584 6515582760898265088 7939846143054184448 9093893547567874048 4099401560813993984 8277616115106971648 -8488159397686542336 410953465997557760 2596325185179090944 -8106479329266892800 5406571352658280448 102456891522678784 1804817550668726272 2543407889557487616 4242390848983007232 3638908498915360768 8533195393960247296 9181713740301598720 8807914971229847552 1378101485975371776 8267483015945388032 4738912707900604416 8718968878589280256 2216896916573126656 1313925191285342208 4178214554292977664 5107081977438142464 496521858917597184 5522539043063070720 3561221405343219712 5244441766072942592 4971973988617027584 -7894810146780479488 3422735716801576960 3862962580377042944 -7734932360008826880 -7524389077429256192 1531223873305968640 7567173273889275904 882705526964617216 980658818859925504 3360811221925232640 -9160321642071588864 9019584153716260864 637259347272925184 4687121312185843712 7689896363735121920 8918253162100424704 2306968909120536576 7607705670535610368 6413125869375586304 -8688569581104529408 6981705322331111424 -7799108654698856448 
50  time: 0.000229423
50  time: 0.001806263

main関数

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"time"
)

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Scan()
	
	n, _ := strconv.Atoi(sc.Text())
	
	nums := make([]int, n)
	
	for i := 0; i < n; i++ {
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())
		nums[i] = k
	}
	
	t0 := time.Now()
	ans, _ := solve(0, nums)
	t1 := time.Now()
	fmt.Println(ans, " time:", t1.Sub(t0).Seconds())
	
	t2:=time.Now()
	ans2:=solveAtOnce(nums)
	t3:=time.Now()
	fmt.Println(ans2," time:",t3.Sub(t2).Seconds())
}

func divideByTwo(nums []int) ([]int, bool) {
	nums2 := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		n := nums[i]
		if n%2 == 0 {
			nums2[i] = n / 2
		} else {
			return nums, false
		}
	}
	return nums2, true
}

func solve(i int, nums []int) (int, []int) {
	nums2, t := divideByTwo(nums)
	if !t {
		return i, nums
	}
	return solve(i+1, nums2)
}

func solveAtOnce(nums []int) int {
	for k := 1; ; k++ {
		for _, num := range nums {
			if num%int(math.Pow(2, float64(k))) != 0 {
				return k - 1
			}
		}
	}
}

Answer 1

毎回int(math.Pow(2, float64(k))という型変換とべき乗計算を行っているのが実行時間が遅い要因担っているのかもしれません。

そうだと思います。
(任意の数の)冪乗の計算は非常に遅い命令です(※)。Goの実装は知りませんが、素直に浮動小数点数の冪乗命令を呼んでいるなら、結果に疑問はありません。
たぶんこれはシフトで済みますよね?

※
2^X-1を計算するF2XM1命令というのがあって、まあ素直に考えるとこの命令を使うことになるのですが、これがこちらの表によると例えばSkylakeで実行に65-80クロック掛かるようです(レイテンシ)。
https://www.agner.org/optimize/instruction_tables.pdf
実際には冪乗の計算はこの命令を使わずにする方法もあるようですが、まあそれで格段に速くなるということもないでしょう。