Pythonの再帰関数で漸化式の計算する

目次

単純な漸化式

次のように定義される数式{a_n}の一般項を求めます。

$a_1=1,    a_{n+1}=a_n+4$

漸化式を解くと一般項は次の通りです。

$a_n=4n-3$

これをPythonの再帰関数と一般項の式を使って、n=1から5まで計算し比較します。。

def recurrence(n):
    if n ==1:
        return 1
    else:
        return recurrence(n-1)+4
    
for i in range(1,6):
    print(i,recurrence(i),4*i-3)
1 1 1
2 5 5
3 9 9
4 13 13
5 17 17

簡単な漸化式は、再帰関数で計算することができます。

少し複雑な漸化式

次のように定義される数式{a_n}の一般項を求めます。

$a_1=3,\hspace{5pt}a_{n+1}=3a_n+2n+3$

$a_n=2\cdot3^n-n-2$

def recurrence(n):
    if n ==1:
        return 3
    else:
        return 3*recurrence(n-1)+2*(n-1)+3
    
for i in range(1,6):
    print(i,recurrence(i),2*3**(i)-i-2)
1 3 3
2 14 14
3 49 49
4 156 156
5 479 479

少し複雑なものでも簡単に計算できます。

3項間漸化式

次のように定義される数式{a_n}の一般項を求めます。

$a_1=1,a_2=2\hspace{5pt}a_{n+2}=2a_{n+1}+15a_n$

$a_n=\displaystyle \frac{5^n-(-3)^n}{8}$

from fractions import Fraction
def recurrence(n):
    if n ==1:
        return 1
    if n==2:
        return 2
    else:
        return 2*recurrence(n-1)+15*recurrence(n-2)
    
for i in range(1,6):
    print(i,recurrence(i),Fraction(5**i-(-3)**i,8))
1 1 1
2 2 2
3 19 19
4 68 68
5 421 421

3項間漸化式でも計算できてしまいました。

この記事を書いた人

目次
閉じる