Немного про познание рекурсии

Для того, чтобы познать рекурсию, надо познать рекурсию.
http://bash.im/quote/11128

Познавать рекурсию нужно с детства, я так считаю. Когда родители вручают ребёнку счётные палочки, речь должна идти только о том, что каждое следующее число есть предыдущее число, увеличенное на единицу.

int getNthNumber(int n) {
    int nthNumber = getNthNumber(n-1) + 1;
    return nthNumber;
}

Ну, конечно, обязательно нужно оговориться, что первое число равно нулю

int getNthNumber(int n) {
    if (n == 1) // первое число равно нулю по определению
        return 0;
    int nthNumber = getNthNumber(n-1) + 1;
    return nthNumber;
}

Хотя, в примере выше есть ошибка, в нём нулю равно второе число. Потому что если первое число равно нулю, то первый номер первого числа тоже равен нулю, а не единице (вот это утверждение уже имеет отчётливый привкус рекурсии)

int getNthNumber(int n) {
    if (n == 0) // первое число равно нулю по определению
        return 0;
    int nthNumber = getNthNumber(n-1) + 1;
    return nthNumber;
}

Имея на руках такой мощный инструмент, мы можем практически свернуть горы. Например, можно использовать его для получения любого числа из таблицы Пифагора. Да, давайте так и сделаем. Алгоритм будет модификацией имеющегося у нас метода, только число увеличивается не на единицу, а на заданное значение.

int getPythagoreanNumber(int n, int incr) {
    if (n == 0) // первое число равно нулю по определению
        return 0;
    int nthNumber = getPythagoreanNumber(i-1, incr) + incr;
    return nthNumber;
}

И теперь оказывается, что любое число – это частный случай, потому что его можно выразить как число из таблицы Пифагора (ух, сколько тут рекурсии!)

int getNthNumber(int n) {
    return getPythagoreanNumber(n, 1);
}

Но я так считаю, что без дальнейшей оптимизации познание рекурсии ребёнком со счётными палочками не может считаться оконченным. Теперь, когда мы имеем базовое представление о том, что такое рекурсия, можно начинать пытаться её понять. Для начала, можно представить себе, что же там происходит внутри

int getPythagoreanNumber(int n, int incr) {
    int recursionLevel = 0;
    for (int i = n; i > 0; i--) {
        // мы опускаемся на самый глубокий уровень рекурсии
        recursionLevel++;
    }

    int nthNumber = 0; // первое число равно нулю по определению
    while (recursionLevel-- > 0) {
        // и вычисляем нужное нам значение, постепенно выбираясь из тёмных рекурсивных глубин
        nthNumber = nthNumber + incr;
    }
    return nthNumber;
}

Выглядит довольно мрачно. Конечно, мы можем убрать лишнее:

int getPythagoreanNumber(int n, int incr) {
    int nthNumber = 0; // первое число равно нулю по определению
    for (int recursionLevel = n; recursionLevel > 0; recursionLevel--) {
        nthNumber += incr;
    }
    return nthNumber;
}

Вот теперь можно начинать рассказывать ребёнку, что такое умножение.

P.S. Написал всё это просто для того, чтобы посмотреть, как работает замечательная подсветка синтаксиса от Prism.js в этих странных шаблонах с "динамическим просмотром".