c++ recursion

c++_recursion.md

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