یکی از اصول تفکر محاسباتی توانایی شکستن مسأله به زیرمسائل است (بعد از یافتن الگو). این رو می‌دونیم! حال اگر زیر مسائل مشابه مسأله اصلی باشند اما با اندازه کوچکتر می‌توان از تکنیک توابع خوداتکاء بهره برد. این عبارت اندازه کوچکتر هم خیلی مهم است (چرا که قرار است این شکستن به زیرمسئله یک جایی پایان پذیرد).
ترجمه‌های توابع باز وقوع یا باز فراخوانی‌شونده نیز از ترجمه ضعیف تابع بازگشتی بهتر است اما ما از ترجمه توابع خوداتکاء استفاده می‌کنیم. بازگشت ترجمه کلمه return است و ترجمه کلمه recur (Recursive Function) به معنای تکرار انجام یک کار است. اما کمی عمیق‌تر و با تأمل بیشتر، در این بافتار (Context) ترجمه خوداتکاء به نظر بسیار پرمغز انتخاب شده است. اینکه در این روش، یک تابع برای انجام کارش به خودش اتکا کرده است (تکیه کرده است).
برای اینکه مسئله‌ای بتواند به روش خوداتکاء حل شود باید یک ویژگی اساسی داشته باشد که عبارت است از: مسئله اصلی (مسئله‌ای که به ما داده می‌شود) قابل خرد شدن به زیر مسئله‌هایی از همان نوع مسئله اصلی باشد، به شرطی که اندازه زیر مسئله‌های ایجاد شده کمتر (کوچکتر) باشد.
چه زمانی از روش توابع خوداتکاء استفاده کنیم؟
شخصاً با توضیحات بالا به نظرم می‌رسد پاسخ به این سؤال داده شد اما با این حال می‌توان این‌گونه به طور شهودی، بیان کرد:
برای روشن‌شدن مورد دوم از مسأله مرتب‌سازی و روش حل مرتب‌سازی ادغامی استفاده می‌کنیم:
روش کار (الگوریتم) بدین‌صورت است:
۱- تقسیم آرایه (اعدادی که قرار است مرتب شوند) به دو بخش
۲- بازگشت به مرحله ۱ در صورتی که هنوز طول آرایه بیشتر از یک است
۳- ادغام دو آرایه مرتب
در این مثال، عمل سوم زمانی باید انجام شود که دو عمل ۱ و ۲ به اتمام رسیده باشند. با توجه به اینکه آدرس بازگشت توابع فراخوانی‌شده در مرحله ۲، توسط سیستم در پشته ذخیره شده است بنابراین این تضمین وجود دارد که عمل ادغام به ترتیب از آخر به عمل انجام می‌شود (می‌دانید که به طور کلی وقتی در برنامه تابعی فراخوانی می‌شود کنترل برنامه از محل فعلی به محل تابع فراخوانده شده منتقل می‌شود و آدرس محل فعلی ذخیره می‌شود. پس از پایان یافتن تابع، کنترل برمی‌گردد به مکان فراخوانی که آدرس آن از قبل نگه داشته شده است). مرتب‌سازی به شیوه ادغامی را می‌توان به شیوه مستقیم (بدون استفاده از توابع خوداتکاء) هم نوشت اما پیاده‌سازی پشته حداقل کار اضافه‌ای است که شما به عنوان برنامه‌نویس باید انجام دهید.
همیشه استفاده از توابع خوداتکاء بهتر است؟
خیر، مثال محسوس و دقیق آن پیاده‌سازی تابع فیبوناچی (Fibonacci) به روش خوداتکاء است که زمان اجرای آن نمایی می‌شود که علت آن هم محاسبه چندباره یک سری عبارت است.
به شکل زیر توجه کنید؛ همانطور که مشخص است مثلاً برای محاسبه جمله ۵ام دنباله فیبوناچی، ۲ بار جمله سوم و ۳ بار جمله دوم محاسبه شده است که این انجام کار اضافه منجر به نمایی‌شدن زمان حل مسأله می‌شود. برای درک بهتر محاسبه جمله ششم فیبوناچی را به رسم درخت زیر محاسبه کنید. گوشه ذهنتون داشته باشید یک شیوه بهبود این شرایط، روش Memoization است.
توابع خوداتکاء و برنامه‌نویسی تابع‌گرا (Functional Programming)
این بخش برای علاقمندان به سبک برنامه‌نویسی تابع‌گرا یا همان Functional Programming به این نوشته اضافه شده است. در برنامه‌نویسی تابع‌گرا ترجیح بر این است که تا حد امکان از حلقه کمتر استفاده شود و همه کارهای با استفاده از توابع انجام شود. در این سبک برنامه‌نویسی می‌توان برای ایجاد تکرار به جای استفاده از حلقه از توابع خوداتکاء بهره برد.
