سلام.
خیلی سوال جالبیه
کار این تابع اینه که :
[tex]\binom{n}{k}[/tex] رو مرتبا به مسائل کوچیک تقسیم میکنه تا به یک برسه و آخر سر ۱ های به دست آمده با هم جمع میشوند.

یعنی برای ساختن [tex]\binom{n}{k}[/tex] باید [tex]\binom{n}{k}-1[/tex] بار عمل + انجام دهیم از طرفی عمل + به دوبار صدا زدن تابع احتیاج داره پس تابع به تعداد :
[tex]2\binom{n}{k}-2[/tex]
احتیاج دارد.

چون توی صورت تست تعداد بازگشتی رو خواسته میشه گزینه ی ۳

اگر اولین صدا زدن در تابع اصلی رو در نظر بگیریم میشود گزینه ی یک
===========
یادمه توی دوتا تست سراسری آی تی برای الگوریتم ضرب استراسن هم چنین ایده ای به کار گرفته شده بود