やねう企画2005年入社問題解答と解説

やねう企画2005年入社問題(id:yaneurao:20050929)の解答と解説。

問1.
f(x,y)が数学的関数(要するに、x,yが定まれば値がひとつ定まる関数)であることは見れば気づくはず。fの再帰停止条件はx==1 || x==yで、この時の返し値は1。よって、g(a) = bだとしたら、少なくともfはb回呼び出されていることを意味する。この呼び出し回数をどうやって減らすのかというのがひとつ目の着眼点。