# Recursive Algorithm

### What is Recursive function
A recursive function. is a function that call itself during runtime, until it reach a base condition, which is a condition will stop the recursion.

### How recursive function work
Recursive function will call itself within its code block. Each call to the function will save the context of the current function to stack. Once the base case is reached, the function stops calling itself, and the stack context of the context will be recover, returning control back up through the recursive calls.

### When I need to use recursive function
When you have a complex problem that cannot get the answer, and you know there have base conditions can get the answer directly. So you can use recursive function to solve the problem.

## Fibonacci sequence

int f(int x) {
    if (x > 1) return f(x - 1) + f(x - 2);
    return x;
}

## Hanoi Tower
Before solve this question we need to find out the solution of the hanoi tower game. Firstly, if $n = 1$, we can directly move the plate from start rod to end rod. If $n > 1$, we can simplify the problem to the subproblem.

Now we have three rods, name it `a`, `b` and `c`. The plates initial position is `a`, and we need move it to `c`. If there have $n$ plates, this is the solution that how we can solve it:

1. Find the solution that move $n-1$ plates to `b` from `a`.
2. Move the $n$th plate to `c`.
3. Find the solution that move $n-1$ plates to `c` from `b`.

The solution look simple, how can we solve the complex problem in this simple way? If we know how 1 plate move to the destination, we will find out how 2 plates move to the destination. According this logic, we can find out a way that move n plates to the destination.

This is the example code:

#include <iostream>
using namespace std;

void hanoi(int n, char start, char mid, char end) {
    if (n == 1) {
        cout << start << " -> " << end << endl;
        return;
    }
    hanoi(n - 1, start, end, mid);
    cout << start << " -> " << end << endl;
    hanoi(n - 1, mid, start, end);
}

int main() 
{
    int n; cin >> n;
    hanoi(n, 'a', 'b', 'c');

    return 0;
}

1. If $n = 1$, we just need move the plate to the end position.

This is the base condition in this recursive function.

1. If $n > 1$, we need find out a way to move $n-1$ plates from `start` to `mid`.
2. After we move $n-1$ plates to `mid`, we can move the $n$th plate to `end`.
3. And we need to find out a way to move $n-1$ plates from `mid` to `end`.

When the $n$ keep decrease until it reach value $1$, we will get the $2,3,4,...,n$ plates solution.

## Permutation

Get permutation results we need to use backtracking algorithm to put the value in the sequence one by one. In the backtracking algorithm need to use recursive function to implement it.

### When we need to use backtracking algorithm

When we need to try every sequences, we can use backtracking algorithm to get the sequences and try it is fulfill the condition of the problem.

### How to implement backtracking algorithm

**Define a condition to end the recursion**
When all the node value you visited or the list is full, you can get the result and return back to get the new sequence.

**How to generate every results?**
Set every element are not visited, when you visit the element in the backtracking algorithm, we need to set the element visited, to prevent the element visit again.

#include <iostream>
using namespace std;

int n;
vector<int> v;
vector<bool> vis;

void generate_permutation(int k) {
    if (n == k) {
        for (auto x : v) cout << x << " "; cout << endl;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        vis[i] = true;
        v.push_back(i + 1);
        generate_permutation(k + 1);
        v.pop_back();
        vis[i] = false;
    }
}

int main() 
{
    cin >> n;
    vis.resize(n, false);
    generate_permutation(0);

    return 0;
}