حمزه قائم پناه
حمزه قائم پناه
خواندن ۲ دقیقه·۱ سال پیش

چطور از پس سوالات بازگشتی (Recursion) بربیایم؟

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

یک مسال ساده حساب کردن فاکتوریل یک عدده که به این صورت حساب میشه:

5 Factorial = 5! = 5*4*3*2*1

شناسایی سوالات بازگشتی:

دنبال این نشانه‌ها توی سوالات باش:

  • سوال می‌تونه به زیرمساله‌هایی که مشابه مساله اصلی هستن بشکنه. (در مثال ما ۵! می‌تونه به ۵*۴! شکسته بشه)
  • یک مورد پایه تو سوال وجود داره که ساده‌ترین نمونه مشکله و میشه مستقیم به راحتی حلش کرد. (در مثال ساده‌ترین حالت ۰! = ۱ هست)
  • مساله می‌تونه در قالب خودش بیان بشه.

بخش‌های اصلی الگوریتم بازگشتی:

  • مورد پایه (Base Case): این شرایطی هست که چرخه بازگشت رو متوقف می‌کنه. نماینگر ساده‌ترین حالت سواله و مستقیما پاسخ رو ارائه میده.
  • مورد بازگشتی (Recursive Case): این بخش الگوریتم، تابع خودش رو مجدد با نسخه تغییر پیدا کرده مساله، صدا میزنه. این بخش باید نزدیک base case باشه.
  • آرگومان‌های تابع (Function Arguments): تابع باید آرگومان‌هایی بگیره که نمایانگر وضعیت مساله باشه. این آرگومان‌ها معمولا در هر فراخوانی تابع تغییر می‌کنن.

این یک نمونه ساده از تابع بازگشتیه:

def factorial(n): # Base case if n == 0: return 1 # Recursive case else: return n * factorial(n - 1)

بازگشت به عقب در بازگشتی: (Backtracking in Recursion)

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

دو بخش اصلی این مسائل دارن:

  • شروع با راه‌حل اولیه و ساختن بر اون اساس
  • در هر گام، تصمیم‌گیری کردن، اون انتخاب رو ادامه دادن و درصورتی که به بن‌بست رسید نادیده گرفتن و به حالت اولیه برگردوندنش.

به طور مثال مساله N Queen که می‌خوایم ببینیم به چند حالت میشه وزیر رو در یک شطرنج N * N قرار داد که مطمئن بود همدیگه رو نمی‌تونن بزنن.

ساختار کلی حل مساله به این صورت هست:

def solve_n_queens(n): def is_safe(board, row, col): # Check if it's safe to place a queen at board[row][col] # Implementation depends on the problem def solve(board, row): if row >= n: # All queens are placed # Add the board configuration to the result for col in range(n): if is_safe(board, row, col): board[row][col] = 'Q' # Place a queen solve(board, row + 1) board[row][col] = '.' # Backtrack board = [['.' for _ in range(n)] for _ in range(n)] solve(board, 0)


سوالات بازگشتیRecursionboard rowrow colحل مساله
مهندس نرم‌افزار و عاشق توسعه فردی - مهندس نرم‌افزار - اکس هم بنیان‌گذار و مدیرفنی و پرداکت استارتاپ کشمون
شاید از این پست‌ها خوشتان بیاید