
再帰の戻り値を呼出し順と逆に計算する
解き方
再帰の問題は、呼び出しを積み上げる段階と、戻り値を受け取る段階を分けると追いやすくなります。各呼出しで使う引数を別々に記録します。
手順を追う例
関数fは、n=0なら1を返し、それ以外なら2×f(n−1)+1を返します。f(3)を求めるときはf(3)、f(2)、f(1)、f(0)の順に呼び出します。
確認問題【オリジナル】
f(3)の値を、f(0)から順に計算してください。
答えと解説
f(0)=1、f(1)=2×1+1=3、f(2)=2×3+1=7、f(3)=2×7+1=15です。停止条件の1を出発点にし、呼出しと逆順に計算します。f(n)=2n+1のように、再帰呼出しの結果を引数nそのものへ置き換えると別の式になります。