تابع کولاتز و پیاده‌سازی آن در پایتون

سلام. بعد مدتی فراغت از نوشتن، می‌خواهم راجع به حدس «کولاتز» بنویسم.

حدس کولاتز Collatz

بیایید یک بازی جالب کنیم.

یک عدد طبیعی را به دلخواه انتخاب کنید. (ترجیحا عدد کوچک باشد)

اگر عدد انتخابی زوج هست، آن را بر دو تقسیم کنید و اگر فرد هست، آن را در ۳ ضرب کنید و حاصل را با یک جمع کنید، سپس بر ۲ تقسیم کنید. این کار را با عدد به دست آمده تکرار کنید.

مثلا من انتخاب کردم ۳

عدد سه فرد هست، ۳ را ۳ برابر می‌کنیم که می‌شود ۹ و آن را با ۱ جمع می‌کنم که می‌شود ۱۰ و ۱۰ را بر دو تقسیم می‌کنم. سیر تحول این عدد به صورت زیر هست:

a: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

یا برای عدد ۱۲

a: 12 -> 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 ->1

سوال: آیا این تابع، برای همه اعداد به یک منتهی می‌شود؟ (بدهی است که وقتی به یک برسد، دیگر عملیات عدد فرد را انجام نمی‌دهد)

هیچ‌کس نمی‌داند! این یکی از معروف‌ترین مسائل حل‌نشده در ریاضی هست.

پیاده‌سازی تابع کولاتز با پایتون

def collatz(n):
  if n=1:
     return True
   elif n%2=0:
      return collatz(n/2)
   elif n==0:
      return &quotما را سر کار گذاشتی؟&quot
   else:
     return collatz(3n+1)

جالب نیست که همین قطعه کد، یکی از مسائل حل نشده بشریت هست؟

توضیح کد

ما یک تابع بازگشتی (بعدا می‌گویم یعنی چه) به نام collatz تعریف کردیم که یک عدد را می‌پذیرد.

با دستورات شرطی مشخص کرده‌ایم که اگر عدد برابر صفر بود، به تابع خاتمه بدهد و مقدار True را برگرداند که نشان می‌دهد به جواب ۱ رسیده‌ایم.

در غیر اینصورت:

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

و اگر زوج نبود (فرد هست دیگر، حالتی دیگر نیست)، آن را ۳برابر کرده و با یک جمع می‌کنیم.

در نهایت جواب را به تابع می‌دهد و تابع به قدری این عملیات را انجام می‌دهد تا به عدد ۱ برخورد کند.

چرا return ؟
شاید با خود بپرسی چرا تابع را return کردم و نوشتم return collatz(x) و نه collatz(x) در حالی که هر دو کار خواهند کرد؟

به یاد بیاورید که ما خواستیم اگر تابع به عدد یک برخورد کرد، مقدار True را برگرداند. حالا فرض کنید یکی از توابع داخلی به مقدار یک رسید و True را برگرداند. اما اگر ما دستور return را ننوشته باشیم، هیچ اتفاقی نمی‌افتاد.

به این توابع که خودشان را صدا می‌زنند، توابع برگشتی (recursive) می‌گویند.
البته، باید این را در نظر داشته باشید که توابع برگشتی، کاملا تعریف می‌شوند و مثلا اینطور نیست که اگر پایتون در یک تابع، ببیند که خودش را فراخوانی کرده، ادامه کد را ندید بگیرد. آن‌ها هم مثل بقیه توابعی هستند که تابع دیگری را صدا می‌زنند.