続：再帰関数 Tree Recursion
前回は再帰関数の基本についてやりました。３つの要素
1. Base case...終了条件
2. Recursive call...再帰表現
3. Solve full problem...２を使って元々の問題を解く
今回もそれに則ってやっていく。
まず、Tree Recursionというのは、基本的に樹形図みたいなもの。
樹形図を書いて、base caseを探して、残りを再帰にしよう的な。その際に、再帰表現が２つ以上になる事が多い（パターンが枝分かれしているから）。
この概念を使うと、フィボナッチ数列を求めるプログラムが簡単に書けるようになる。
まず、フィボナッチ数列というのは、０th＝０、１st＝１として、前の数字と現在の数字を足したものが次の数字になるという数列。つまり、
０、１、１、２、３、５、８、１３、２１、３４、５５、８９、…
という風に増加していく。このn番目の数字が何かを求めるプログラムを書く。
例えば、4番目のフィボナッチ数列を求めたい。この時の樹形図を書くと、
という風になる。フィボナッチ数列の1番目は１、0番目は０なので、この末端の数字を足していくと３となり、フィボナッチ数列4番目の数は３である事がわかる。
この末端のfib(1)とfib(0)をbase caseとして再帰関数でフィボナッチ数列を表す事が出来る（n == 1 の時、 return 1、n == 0 の時、return 0）。
そして出来上がるプログラムがこちら。
この場合のbase caseはn＝０とn＝１の２通り。最後のelse文で再帰表現を二つ使っているのはそのため。
つまり、Tree Recursionの場合も、基本的には終了条件は何か、returnで自身を返しているか、またその表現は終了条件に収束していくかどうかを考えれば良い。
練習問題１
n段の階段がある。この階段を登るとき、１段か２段ずつしか上がらないことにする。この時、何通りの登り方があるかを計算するプログラムを作りなさい。
def count_stair_ways(n):
"""
>>> count_stair_ways(7)
21
>>> count_stair_ways(3)
3 # 1+1+1, 1+2, 2+1
"""
解答
練習問題２
先の問題で１段か２段を上がる代わりに、k以内の段数を登ることにする。この時の登り方が何通りあるかを計算するプログラムを作りなさい。
def count_k(n, k):
"""
>>> count_k(3, 3). # 3, 2+1, 1+2, 1+1+1
4
>>> count_k(4, 4)
8
"""
解答
一応これも再帰関数…
練習問題３
パスカルの三角形の(row, column)の位置の数字を求めるプログラムを作りなさい。
def pascal(row, column):
"""
>>> pascal(2, 1)
2
>>> pascal(4, 2)
6
"""
解答
