c++ recursion

recursion

something references itself
needs a terminating control structure or else will continue forever
good for searching and backtracking
is always slower in c++ than iteration
stack does have a finite amount
every time a recursive function is called, it's call is placed onto the stack and we jump to the function execution, leaving our place in the previous call until the current call is finished
stack overflow is when your call stack is larger than your operating system allows
- usually only with infinite recursion

towers of hanoi

three pegs and a stack of round circles. Must move each circle over to the third peg without a larger circle being placed on a smaller.

header.h:

struct node {
    ~node();
    void display_reverse();
    int data;
    node *next;
}

class list {
    public:
        list(char new_name);
        ~list();
        int remove_first();
        void prepend_first(int new_data);
        void display_reverse();
        char name;
    private:
    node *head;
}

hanoi.cpp

list::list(char new_name) {
    head = NULL;
    name = new_name;
}

node::~node() {
    // allowed to delete NULL
    delete next;
}

list::~list() {
    delete head;
}

list::prepend_first(int new_data) {
    node *new_node = new node;
    new_node->data = new_data;
    new_node->next = head;
    head = new_node;
}

list::remove_first() {
    if (!head) return -1;
    node *temp = head;
    head = head->next;
    // must set next to be null before deleting
    // otherwise would trigger destructor of old head
    // and entire list
    temp->next = NULL;
    int ret = temp->data;
    delete temp;
    return ret;
}

node::display_reverse() {
    // recursive!
    if (next) next->display_reverse();
    cout << data << " ";
}

list::display_reverse() {
    cout << name << ": ";
    if (head) head->display_reverse();
    cout << endl;
}

binary search

takes a sorted array and continuously splits it to find desired value

Theartbug/c++_recursion.md

recursion