* Functions can call themselves, this is called recursion.

void foo()
{
    foo();
}

Infinite loop!

fact(n) = n * fact(n - 1)
fact(0) = 1

int fact(int n)
{
    if(n == 0)
        return 1;
    else
        return n * fact(n - 1);
}

same with sum

sum(n) = n * sum(n-1)
sum(0) = 0

int sum(int n)
{
    if(n == 0)
        return 0;

    return n * sum(n - 1);
}

fib(n) = fib(n-1) + fib(n-2);

int fib(int n) 
{
    if(n == 0)
        return 1;
    if(n == 1)
        return 1;
    return fib(n-1)+fib(n-2);
}

Beware, this is much slower than using a loop.  Why?

every fib, is calculated many many times

fib(9)
fib(8)+fib(7)
(fib(7)+fib(6))+(fib(6)+fib(5))
....

Recursive functions are often much more elegant than loops.  Every loop can be
written as a recursive function, and vice versa.

void forloop(int init, int cond, int step)
{
    if(init < cond) {
        ....
        forloop(init + step, cond, step);
    }
    return;
}

* Arrays

#include <iostream>

int main()
{
    int integers[10];
    int i;

    for(i = 0; i < 10; i++) {
        cout << "Enter number " << i + 1 << ": ";
        cin >> integers[i];
    }

    cout << "The sum of the numbers you entered is: " << sumInts(integers, 10);
    cout << endl;
}

int sumInts(int ints[], int size)
{
    int i;
    int sum = 0;

    for(i = 0; i < size; i++) {
        sum += ints[i];
    }    
}

initializing arrays:

int ints[] = {0, 1, 2, 3, 4};
float floats[] = {0.0, 1.0, 2.0, 3.0, 4.0};
char chars[] = {'D', 'a', 'v', 'i', 'd', 0};

* Lots of algorithms for arrays

int linearSearch(int ints[], size, int key)
{
    for(int i = 0; i < size; i++) {
        if(ints[i] == key)
            return i;
    }

    return -1;
}

* Best you can do if you know nothing about the order of the integers.

* If sorted, you can go much faster

int binarySearch(int ints[], int size, int key)
{
    int low = 0;
    int high = size - 1;
    int mid;

    while(low <= high) {
       mid = (high + low) / 2;

       if(ints[mid] < key) {
           low = mid + 1;
       } else if(ints[mid] < key) {
           high = mid - 1;
       } else {
          return mid;
       }
    }

    return -1;
}

* this can also be written recursively.

int binarySearch(int ints[], int low, int high)
{
    if(low > high) {
        return -1;
    }

    int mid = (high + low) / 2

    if(ints[mid] < key) {
        return binarySearch(ints, mid+1, high);
    } else if(ints[mid] < key) {
        return binarySearch(ints, low, mid-1);
    } else {
       return mid;
    }
}

Getting an array sorted is easier said than done:

void stupidSort(int ints[], int size)
{
    for(int i = 0; i < size; i++) {
        swap(ints[i], ints[findMin(ints,size)]);
    }
}

int findMin(int ints[], int size)
{
    int min = 0;

    for(int i = 1; i < size; i++) {
        min = ints[i] < ints[min] ? i : min;
    }

    return min;
}

------------

void quickSort(int ints[], int low, int high)
{
    if(low < high) {
        int p = partition(ints, low, high);
        quicksort(ints, low, p-1);
        quicksort(ints, p+1, high);
    }
}

int partition(int ints[], int low, int high)
{
    int x = ints[high];
    int i = low - 1;
    for(int j = low; j < high; j++) {
        if(ints[j] <= x) {
            i++;
            swap(ints[i], ints[j]);
        }
    }

    swap(ints[i+1], ints[high]);
    return i+1;
}

* Strings
* null-terminated '\0'

#include <iostream>

int strlen(char s[])
{
    int i;

    for(i = 0; s[i] != '\0'; i++) {}
    return i;
}

int strrep(char s[], char src, char dst)
{
    for(int i = 0; s[i] != '\0'; i++) {
        if(s[i] == src) {
            s[i] = dst;
        }
    }
}

int strcmp(char s1[], char s2[])
{
    for(int i = 0; s1[i] != 0 && s2[i] != 0; i++) {
        if(s1[i] != s2[i]) {
             return s1[i] - s2[i];
        }
    }

    if(s1[i] == 0 && s2[i] != 0) {
        return s2[i];
    } else if(s1[i] != 0 && s2[i] == 0) {
        return s1[i];
    } else {
        return 0;
    }    
}

int main()
{
    const char[] MAGIC_STR = "Hello";
    const char[] EXIT_STR = "exit";
    char str[80];
    bool found = false;

    cout << "Type in the magic string.  Type exit if you give up.\n";

    while(!found) {
        if(strcmp(str, EXIT_STR) == 0) {
            cout << "Try again!\n";
            return 0;
        }
 
        if(strcmp(str, MAGIC_STR) == 0) {
            cout << "Good Job!\n";
            found = true;
        }
    }

    return 0;
}