一題有關遞回程式

Question

int F(int n)
{
if(n<=1)
return 0;
else
return F({n/2}) F([n/2]) 1
}
{n}:表小於等於n的最大正整數
[n]:表大於等於n的最小正整數

說明F(n)呼叫幾次

Answer 1

F(n) 呼叫 2n - 1次
證明:
1. n = 1
F(1) call, 1 <= 1 => return 0;
呼叫 1次 = 2*1 - 1
2. 假設 n = k 時成立 (呼叫 2k - 1次)
n = k＋ 1 時
(a) k = 2m
F(k＋1)
= F(2m＋1) <== call
= F({m＋1/2})＋F([m＋1/2])
= F(m)＋F(m＋1)
=> [call 2m - 1 次]＋[call 2(m＋1) - 1 次]
全部 call [2m - 1]＋[ 2(m＋1) - 1]＋1
= 4m＋1
= 2k＋1
= 2(k＋1) - 1
(b) k = 2m＋1
F(k＋1)
= F(2m＋2) <== call
= F({m＋1})＋F([m＋1])
= F(m＋1)＋F(m＋1)
=> [call 2(m＋1) - 1次]＋[call 2(m＋1) - 1 次]
全部 call [2(m＋1) - 1]＋[ 2(m＋1) - 1]＋1
= 4m＋3
= 2k＋1
= 2(k＋1) - 1
由 歸納法證明成立
如果有問題, 請來函討論. 不然, 我可能會錯失你再補充的疑點.