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

#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;
}
				

#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);
}
				

#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;
}
				

#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);
}
				

#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;
}
				

#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";
    }
}
				

#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);
}
				

#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();
}