تعریف بازگشتی

یک تعریف بازگشتی (یا تعریف استقرایی) در منطق ریاضی و علوم کامپیوتر برای تعریف اعضای یک مجموعه به‌طور وابسته به دیگر اعضا استفاده می‌شود. یک رابطه بازگشتی فرمولی است که جملهٔ n ام را به k جملهٔ پیشین مرتبط می‌سازد.

چهار مرحله در ساخت یک برفدانه کخ. مانند بسیاری دیگر از فرکتال‌ها مراحل از طریق یک تعریف بازگشتی به دست می‌آیند.

تعریف بازگشتی یک تابع مقادیر تابع را برای برخی از ورودی‌ها با در نظر گرفتن اعضای دیگری از همین تابع بیان می‌کند. برای مثال تابع فاکتوریل ($n!$) با دستور زیر تعریف می‌شود:

$0!=1$

$(n+1)!=(n!)(n+1)$ این تعریف برای هر n برقرار است. زیرا با بازگشتن پیاپی از حالت نهایی به سمت عقب، نهایتاً به جملهٔ اولیهٔ صفر می‌رسیم. به عبارتی، این تعریف یک روند برای ساخت تابع $n!$ بیان می‌کند که با شروع از $n=0$ و ادامه دادن با $n=1$ و $n=2$ و … به جملهٔ مورد نظر از این دنباله می‌رسیم.

همان‌طور که گفته شد، تعریف استقرایی یک مجموعه هر عضو مجموعه را بر اساس دیگر اعضای موجود در مجموعه توصیف می‌کند. برای مثال یک تعریف از مجموعهٔ اعداد طبیعی ($\mathbb {N}$) در اینجا ارائه شده‌است:

1. عدد $1$ عضوی از $\mathbb {N}$ است.
2. اگر یک عنصر $n$ عضو $\mathbb {N}$ باشد، $n+1$ نیز عضوی از $\mathbb {N}$ است.
3. $\mathbb {N}$ اشتراک تمام مجموعه‌هایی ست که در شروط بالا صدق کند.

مجموعه‌های بسیاری در شروط ۱ و ۲ صدق می‌کنند. مثلاً مجموعهٔ زیر را در نظر بگیرید: {${1,1.649,2,2.649,3,3.649,...}$} این مجموعه در شروط یک و دو ی بالا صدق می‌کند. اما شرط سه مجموعهٔ اعداد طبیعی را با حذف اعضای فرعی به وجود می‌آورد.

ویژگی‌های توابع و مجموعه‌های تعریف شده به صورت بازگشتی را اغلب می‌توان با استقرای ریاضی ثابت کرد. برای مثال تعریف اعداد طبیعی ارائه شده در اینجا به‌طور مستقیم به اصل استقرای ریاضی برای اعداد طبیعی دلالت می‌کند: اگر یک ویژگی برای عدد ۰ برقرار باشد و از برقراری آن ویژگی برای $n$ بتوان درستی آن را برای $n+1$ نیز نشان داد، آن ویژگی برای تمام اعداد طبیعی برقرار خواهد بود.

قالب تعاریف بازگشتی

اکثر تعاریف بازگشتی بر دو اساس استوارند: یک یا چند جملهٔ پایه و یک شرط استقرایی.

تفاوت بین تعریف دایره ای و تعریف بازگشتی این است که یک تعریف بازگشتی باید همیشه حالت پایه داشته باشد. در مقابل یک تعریف دایره‌ای هیچ پایه‌ای ندارد و مقدار یک تابع را با توجه به خود آن تعریف می‌کند. این باعث می‌شود که تا بی‌نهایت مجبور به بازگشت باشیم.

این مسئله که کدام تعاریف بازگشتی قابل قبول اند - به این معنی که یک تابع منحصر به فرد را توصیف کنند - یک قضیه از نظریه مجموعه‌ها است که اثبات آن چندان بدیهی نیست. اگر دامنهٔ تابع اعداد طبیعی باشد، برای آنکه تعریف قابل قبول باشد باید اولاً حالت پایه مشخص باشد. دوماً برای n>0 یک الگوریتم برای تعیین جملهٔ n ام بر اساس اعضای مشخص مجموعه وجود داشته باشد.

به‌طور کلی، تعریف بازگشتی یک تابع در صورتی می‌تواند ایجاد گردد که دامنه آن خوش ترتیب باشد.

مثال‌هایی از تعاریف بازگشتی

توابع مقدماتی

عمل جمع به صورت بازگشتی تعریف می‌شود:

$0+a=a$

$(1+n)+a=1+(n+a)$

تعریف بازگشتی ضرب اعداد چنین است:

$0a=0$

$(1+n)a=a+na$

توان به صورت بازگشتی به شکل زیر تعریف شده‌است:

$a^{0}=1$

$a^{1+n}=aa^{n}$

ضرایب دوجمله‌ای به صورت بازگشتی به فرم زیر تعریف می‌گردند:

${\binom {a}{0}}=1$

${\binom {1+a}{1+n}}={\frac {(1+a){\binom {a}{n}}}{1+n}}$

اعداد اول

مجموعه اعداد اول را می‌توان به عنوان مجموعه‌ای منحصر به فرد از اعداد صحیح مثبت توصیف کرد. کافی ست اعضای آن مطابق با تعریف بازگشتی زیر باشند:

• ۱ عدد اول نیست
• هر عدد صحیح مثبت دیگر اول است اگر و تنها اگر بر هیچ‌یک از اعداد اول کوچکتر از خودش بخشپذیر نباشد.

اول نبودن عدد یک، حالت پایه در این تعریف است. برای بررسی اول بودن هر عدد صحیح بزرگتر از یک مانند X با استفاده از این تعریف، باید اول بودن یا نبودن هر عدد صحیح بین ۱ و X را بدانیم.

اعداد زوج نا منفی

اعداد زوج می‌تواند به صورت زیر تعریف شوند:

• ۰ در مجموعه اعداد زوج نامنفی (E) است (حالت پایه)
• برای هر عنصر x در این مجموعه x+2 نیز در آن است (تعریف استقرایی)
• هیچ چیز در E نیست مگر اینکه از حالت پایه و تعریف استقرایی بالا نتیجه شود.

فرمول خوش فرم

تعاریف بازگشتی عمدتاً در منطق یا برنامه‌نویسی یافت می‌شوند. برای مثال فرمول‌های خوش فرم در منطق گزاره ای چنین بیان می‌شوند:

1. T و F و p خوش فرم هستند. (p یک متغیر گزاره‌ای است)
2. اگر E و F خوش فرم باشند، (E¬) و (E ∧ F) و (E ∨ F) و (E → F) و (E ↔ F) هم خوش فرم هستند.

منابع

• ویکی‌پدیای انگلیسی