بخش ۵ - مقدمه‌ای بر توابع بازگشتی

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

فهرست مثال‌ها

محاسبه‌ی فاکتوریل

این برنامه به روش بازگشتی فاکتوریل یک عدد را محاسبه می‌کند. ایده‌ی اصلی در حل این مسئله بر این رابطه استوار است که برای n>1 داریم n!=n*(n-1)!.

01_Factorial.cpp
#include <iostream>
using namespace std;
int fact(int n)
{
    if (n <= 1)
        return 1;
    else
        return n * fact(n - 1);
}

int main()
{
    int num;
    cout << "Enter a positive integer number: ";
    cin >> num;
    int num_fact = fact(num);
    cout << num << "! = " <<  num_fact << endl;
}
				
حل مسئله‌ی برج هانوی به طور بازگشتی

سه میله به نام‌های a و b و c داریم که میله‌ی a در ابتدا حاوی n قرص با اندازه‌های متفاوت است طوری که از بالا به پایین اندازه‌ی قرص‌ها زیاد می‌شود. هدف منتقل کردن تمام قرص‌ها به میله‌ی b است با این شرط که اولاً هربار فقط یک قرص منتقل شود و ثانیاً هیچ‌وقت یک قرص روی قرص کوچک‌تر قرار نگیرد. از میله‌ی c نیز می‌توان کمک گرفت. [اطلاعات بیشتر در ویکی‌پدیا]

02_Hanoi.cpp
#include <iostream>
#include <vector>
using namespace std;

// definition of the three pegs
vector<int> a;
vector<int> b;
vector<int> c;

void print_peg(vector<int> peg)
{
    for (int i = 0; i < peg.size(); i++)
        cout << peg[i] << ' ';
    cout << '\n';
}

void print_pegs()
{
    cout << "A: ";
    print_peg(a);
    cout << "B: ";
    print_peg(b);
    cout << "C: ";
    print_peg(c);
    cout << endl;
}

void move(vector<int>& from_peg, vector<int>& to_peg)
{
    to_peg.push_back(from_peg.back());
    from_peg.pop_back();
    print_pegs();
}

void hanoi(vector<int>& from, vector<int>& to,
           vector<int>& _using, int num_of_discs)
{
    if (num_of_discs == 1)
        move(from, to);
    else {
        hanoi(from, _using, to, num_of_discs - 1);
        move(from, to);
        hanoi(_using, to, from, num_of_discs - 1);
    }   
}

int main()
{
    int num_of_discs;
    cout << "How many discs? ";
    cin >> num_of_discs;

    for (int i = num_of_discs; i >= 1; i--)
        a.push_back(i);

    print_pegs();
    hanoi(a, b, c, num_of_discs);
}
				
محاسبه‌ی مجموع اعداد

در این مثال، مجموع اعداد موجود در یک بردار را به صورت بازگشتی محاسبه می‌کنیم.

اگر از پارامتر اضافه‌ی i خوشتان نمی‌آید می‌توانید از زبان‌های برنامه‌نویسی استفاده کنید که امکان جدا کردن «سر» یک لیست را از «بقیه‌» (یا «دم») آن را به راحتی مهیا می‌کنند. تعریف این تابع در زبان ارلانگ (Erlang) به شکل زیر است:

sum_list( [Num] ) -> Num;
sum_list( [Head | Tail] ) -> Head + sum_list(Tail).

03_SumList.cpp
#include <iostream>
#include <vector>
using namespace std;

int sum_list(vector<int> list, int i)
{
    if (i == list.size())
        return 0;
    else
        return list[i] + sum_list(list, i + 1);
}

int main()
{
    vector<int> a;
    int x;
    while (cin >> x)
        a.push_back(x);

    cout << "sum = " << sum_list(a, 0) << endl;
}
				
مرتب‌سازی انتخابی

در این مثال الگوریتم مرتب‌سازی انتخابی (selection sort) به طور بازگشتی پیاده‌سازی می‌شود.

04_SelSort.cpp
#include <iostream>
#include <vector>
using namespace std;

void swap(int& a, int& b)
{
    int temp = a;
    a = b;
    b = temp;
}


int min_index(vector<int> list, int i)
{
    if (i == list.size() - 1)
        return i;

    int min_idx_rest = min_index(list, i + 1);
    if (list[i] < list[min_idx_rest])
        return i;
    else
        return min_idx_rest;
}

void selection_sort(vector<int>& list, int i)
{
    if (i == list.size())
        return;
    int j = min_index(list, i);
    swap(list[i], list[j]);
    selection_sort(list, i + 1);    
}

void print_list(vector<int> list, int i)
{
    if (i == list.size())
        cout << endl;
    else {
        cout << list[i] << ' ';
        print_list(list, i + 1);
    }
}

int main()
{
    vector<int> a;
    int x;
    while (cin >> x)
        a.push_back(x);
    
    selection_sort(a, 0);
    print_list(a, 0);
}
				
جستجوی دودویی

در این مثال الگوریتم جستجوی دودویی برای یافتن یک عنصر در لیستی مرتب از اعداد پیاده‌سازی شده است.

05_BSearch.cpp
#include <iostream>
#include <vector>
using namespace std;

int binary_search(vector<int> list, int from, int to, int key)
{
    if (list.size() == 0)
        return -1;
    if (from > to)
        return -1;

    int mid = (from + to) / 2;
    if (list[mid] == key)
        return mid;
    else if (list[mid] < key)
        return binary_search(list, mid + 1, to, key);
    else
        return binary_search(list, from, mid - 1, key);
}

int main()
{
    const int key = 19;

    cout << "Enter a sorted list of integers. I will look for 19 in the list! ";
    vector<int> a;
    int x;
    while (cin >> x)
        a.push_back(x);
    
    int idx = binary_search(a, 0, a.size() - 1, key);
    
    if (idx == -1)
        cout << "key not found" << endl;
    else
        cout << "key is found at index " << idx << endl;
}
				
محاسبه‌ی دنباله‌ی فیبوناچی

در این مثال اعداد دنباله‌ی فیبوناچی به طور بازگشتی و غیربازگشتی محاسبه خواهند شد. مقایسه‌ی زمان اجرای دو نوع پیاده‌سازی این تابع حاوی نکاتی جالب توجه است.

06_Fib.cpp
#include <iostream>
#include <ctime>
using namespace std;

long fib(long n)
{
    if (n <= 2)
        return 1;
    return fib(n - 1) + fib (n - 2);
}

long nr_fib(long n)
{
    if (n <= 2)
        return 1;
    long a = 1;
    long b = 1;
    long c;
    
    for (long i = 0; i < n - 2; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

int main()
{
    clock_t t;
    for (int n = 1; n < 50; n++) {
        cout << "n=" << n << '\t';
        
        t = clock();
        long f = nr_fib(n);
        t = clock() - t;
        cout << "Non-Rec: " << 1000*t/CLOCKS_PER_SEC << "(ms)\t";

        t = clock();
        f = fib(n);
        t = clock() - t;
        cout << "Rec: " << 1000*t/CLOCKS_PER_SEC << "(ms)\n";
    }
}
				
مسئله سفر اسب

در این مثال، مسئله‌ی معروف سفر اسب در صفحه شطرنج با روش عقب‌گرد (backtracking) حل می‌شود.

07_Knight.cpp
#include <iostream>
using namespace std;

const int ROW_COUNT = 7;
const int COL_COUNT = 7;
const int POSSIBLE_MOVES = 8;

int row_delta[POSSIBLE_MOVES] = {2, 1, -1, -2, -2, -1, 1, 2};
int col_delta[POSSIBLE_MOVES] = {-1, -2, -2, -1, 1, 2, 2, 1};

int board[ROW_COUNT][COL_COUNT];

bool print_board() {
    for (int i = 0; i < ROW_COUNT; i++) {
        for (int j = 0; j < COL_COUNT; j++) {
            if (board[i][j] < 10)
                cout << ' ';
            cout << board[i][j] << ' ';
        }
        cout << endl;
    }
    cin.get();
}

bool find_tour(int move_no, int current_row, int current_col) {
    // uncomment the following two lines for debugging:
    // cout << move_no << endl;
    // print_board();
    
    if (move_no == ROW_COUNT * COL_COUNT)
        return true;
        
    for (int move = 0; move < POSSIBLE_MOVES; move++) {
        int new_row = current_row + row_delta[move];
        int new_col = current_col + col_delta[move];
        
        if (new_row < 0 || new_row >= ROW_COUNT || new_col < 0 || new_col >= COL_COUNT)
            continue;
            
        if (board[new_row][new_col] != 0)
            continue;
            
        board[new_row][new_col] = move_no + 1;
        if (find_tour(move_no + 1, new_row, new_col))
            return true;
        board[new_row][new_col] = 0;
    }
    return false;
}

void solve(int init_row, int init_col) {
    for (int row = 0; row < ROW_COUNT; row++)
        for (int col = 0; col < COL_COUNT; col++)
            board[row][col] = 0;
        
    board[init_row][init_col] = 1;
    if (find_tour(1, init_row, init_col))
        print_board();
    else
        cout << "Failed to find a tour!\n";
}

int main() {
    solve(2, 3);
}
				
مسئله هشت وزیر

در این مثال، مسئله‌ی معروف هشت وزیر در صفحه شطرنج با روش عقب‌گرد (backtracking) حل می‌شود.

08_queens.cpp
#include <iostream>
#include <cmath>
using namespace std;

const int SIZE = 8;

int queen_col_in_row[SIZE];

bool threat(int r1, int c1, int r2, int c2) {
    return (r1 == r2 || c1 == c2 || abs(r1 - r2) == abs(c1 - c2));
}

bool safe_to_put_at(int row, int col) {
    for (int prev_row = 0; prev_row < row; prev_row++)
        if (threat(row, col, prev_row, queen_col_in_row[prev_row]))
            return false;
    return true;
}

void print_board() {
    for (int row = 0; row < SIZE; row++) {
        for (int col = 0; col < SIZE; col++)
            cout << (col == queen_col_in_row[row] ? "QQ" : "..");
        cout << endl;
    }
    cin.get();
}

bool solve(int row) {
    // uncomment the following two lines for debugging:
    // cout << row << endl;
    // print_board();

    if (row == SIZE)
        return true;
        
    for (int col = 0; col < SIZE; col++) {
        if (safe_to_put_at(row, col)) {
            queen_col_in_row[row] = col;
            if (solve(row + 1))
                return true;
            queen_col_in_row[row] = 0;
        }
    }
    return false;
}

int main() {
    for (int row = 0; row < SIZE; row++)
        queen_col_in_row[row] = -1;
    if (solve(0))
        print_board();
}