به نام خدا
رابطۀ بازگشتی در ریاضیات دنباله‌ای است که به‌صورت بازگشتی تعریف می‌شود. برای حل روابط بازگشتی در ریاضیات روش‌های مختلفی وجود دارد، اما با استفاده از نرم‌افزارهای مختلف ریاضی نیز می‌توان روابط بازگشتی را حل کرد (حل یک رابطۀ بازگشتی، یعنی نوشتن یک فرمول بسته برای آن). برای مثال، با وارد کردن کد زیر در نرم‌افزار Maple (میپل)، می‌توانید رابطۀ بازگشتی دنبالۀ فیبوناچی را حل کنید و یک جملۀ عمومی برای دنبالۀ فیبوناچی به‌دست آورید.
rsolve({f(n) = f(n-1) + f(n-2), f(1) = 1, f(2) = 1}, {f});
اما با استفاده از زبان‌های برنامه‌نویسی نیز می‌توان محاسبات ریاضی را انجام داد و حتی روابط بازگشتی را حل کرد. در این مطلب به نحوۀ حل روابط بازگشتی در پایتون می‌پردازم.
برای محاسبات جبریِ نمادین در پایتون، از ماژول sympy استفاده می‌کنیم. این ماژول را در ابتدای کد به شکل زیر وارد می‌کنیم:
from sympy import *
سپس در ادامه می‌نویسیم:
from sympy import *
var('n', integer=True)
a=Function('a')
حالا باید رابطۀ بازگشتی مورد نظر خود را تعریف کنیم. فرض کنید که می‌خواهیم رابطۀ بازگشتی دنبالۀ فیبوناچی را حل کنیم. رابطۀ بازگشتی دنبالۀ فیبوناچی به‌صورت $a_n=a_{n-1}+a_{n-2}$ است که به‌صورت $a_n-a_{n-1}-a_{n-2}=0$ نیز می‌توان آن را نوشت. پس کد f=a(n)-a(n-1)-a(n-2) را به برنامه اضافه می‌کنیم:
from sympy import *
var('n', integer=True)
a=Function('a')
f=a(n)-a(n-1)-a(n-2)
سپس برای حل این رابطۀ بازگشتی و نمایش نتیجه در خروجی، به ترتیب باید از دستورهای rsolve و print استفاده کنیم. کد print(rsolve(f, a(n))) را به برنامه اضافه می‌کنیم:
from sympy import *
var('n', integer=True)
a=Function('a')
f=a(n)-a(n-1)-a(n-2)
print(rsolve(f, a(n)))
سپس برنامه را اجرا می‌کنیم. خروجی به شکل زیر است (دقت کنید که خروجی برنامه همان فرمول بستۀ رابطۀ بازگشتی‌ای است که تعریف کرده بودیم):
C0*(1/2 - sqrt(5)/2)**n + C1*(1/2 + sqrt(5)/2)**n
دقت کنید که ** در پایتون به معنای به توان رساندن است. برای مثال، 2**3 یعنی «2 به توان 3» که 8 می‌شود و sqrt هم همانطور که احتمالاً می‌دانید، به معنای جذر یا ریشۀ دوم است. پس خروجی برنامه را به‌صورت زیر می‌توانیم باز نویسی کنیم:
$$a_n = C_0\bigg(\frac{1}{2}- \frac{ \sqrt{5} }{2} \bigg)^n + C_1\bigg(\frac{1}{2}+ \frac{ \sqrt{5} }{2} \bigg)^n$$
توجه کنید که $C_0$ و $C_1$ دو عدد ثابت هستند که با قرار دادن $n=1$ و $n=2$ و تشکیل یک دستگاه معادله و حل آن، به‌دست می‌آیند.
$$\begin{cases}1=C_0\bigg( \frac{1}{2}- \frac{ \sqrt{5} }{2} \bigg)^1+C_1\bigg( \frac{1}{2}+ \frac{ \sqrt{5} }{2} \bigg)^1 & \\1=C_0\bigg( \frac{1}{2}- \frac{ \sqrt{5} }{2} \bigg)^2+C_1\bigg( \frac{1}{2}+ \frac{ \sqrt{5} }{2} \bigg)^2 & \end{cases} $$
$$ \Longrightarrow (C_0,\space C_1) = \bigg( -\frac{ \sqrt{5} }{5} ,\space \frac{ \sqrt{5} }{5} \bigg)$$
$$ \Longrightarrow a_n = \bigg(-\frac{ \sqrt{5} }{5}\bigg)\bigg(\frac{1}{2}- \frac{ \sqrt{5} }{2} \bigg)^n + \bigg(\frac{ \sqrt{5} }{5}\bigg)\bigg(\frac{1}{2}+ \frac{ \sqrt{5} }{2} \bigg)^n, \space (n\in\mathbb{N})$$
چون دو جملۀ اول دنبالۀ فیبوناچی برابر با یک هستند، در دستگاه معادله در طرف چپ هر دو معادله، عدد یک را قرار دادیم.
می‌توانید خودتان روابط بازگشتی دیگری را نیز به‌همین شکلی که در این مطلب دیدید، با پایتون حل کنید و یک فرمول بسته برای آن‌ها به‌دست آورید.
