حل مساله بازگشتی یک روش حل مساله است که یک تابع، خودش رو برای حل مساله فراخوانی میکنه. مناسب زمانی هست که مساله میتونه به زیر مسالههای کوچکتر و مشابه بشکنه.
یک مسال ساده حساب کردن فاکتوریل یک عدده که به این صورت حساب میشه:
5 Factorial = 5! = 5*4*3*2*1
دنبال این نشانهها توی سوالات باش:
این یک نمونه ساده از تابع بازگشتیه:
def factorial(n): # Base case if n == 0: return 1 # Recursive case else: return n * factorial(n - 1)
بازگشت به عقب یک تکنیکه که شامل بررسی همه راهحلهای ممکن برای یک مشکل و مسیر رو برگشتن در صورتی که راهحلی پیدا نشه، هست. فرق اصلیش با بازگشتی اینه که با اینکه به صورت بازگشتی حل میشه ولی به دنبال ساخت یک راه حل به صورت تدریجی با حذف راهحلهایی که نسبت به محدودیتهای صورت مساله جواب نمیدن هست تا به جواب نهایی برسه. سوالات 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)