申論題

看成一個遞迴函數。終止條件為 fooA(1,1).

也就是說，當 fooA(1,X).的時候，X is 1.

輸入 fooA(N,X) = fooA(3,X) => M is N -1  => fooA(M,Y) = fooA(2,Y)

以此模式繼續往下推導，

=>M' is M -1 => fooA(M', Y') = fooA(1,Y')

抵達終止條件 fooA(1,X) => Y' is 1, 往回傳遞，

Y is 3*Y' + 1 => Y = 3*1+1=4

X is 3*Y + 1 => X = 3*4+1=13.

問題：fooA(5,X) 則 X is ?

用上述邏輯推導：

fooA(5,X) => fooA(4, Y) => fooA(3, Y') => fooA(2, Y'') => fooA(1, Y''')

往回傳遞得到結果：

Y''' = 1;

Y'' = 3*Y'''+1 = 4

Y' = 3*Y''+1 = 3*4+1=13

Y = 3*Y' +1 = 3*13+1=40

X is 3*Y+1 = 3*40+1 = 121

得到答案 X is 121.