Как работает сложение длинных целых в этом примере с рекурсией?

Встретился такой код:
function res(a, b, t, c){ if(a.length == 0 && b.length == 0 && !c) return t; var l = parseInt(a.pop() || '0') + parseInt(b.pop() || '0') + (c || 0); return res(a, b, l + (t || ""), l > 9? 1:0); }
function add(a, b) { return res(a.toString().split(""), b.toString().split(""), "").toString(); }
Судя по всему, код реализует сложение «длинных» целых (функция res() – вспомогательная). Но, похоже, делает это с ошибками. Например, для add(5,5) результат 110, вместо ожидаемого 10, хотя для add(2,3) получается правильный: 5
Я не могу понять, как этот код работает, и где может быть ошибка. Объясните, пожалуйста, доступно.

Ответ

Здесь происходит поразрядное сложение. Таким способом можно складывать как угодно большие числа, не только ограниченные максимально допустимым значением, для js это 1.79E+308, поэтому это называется длинной арифметикой. Поскольку обыкновенные числа ограничены, результат выдаётся в виде строки.
Для начала рассмотрим функцию add
function add(a, b) { return res(a.toString().split(""), b.toString().split(""), "").toString(); }
Предположительно она принимает числа, но может принимать и строку с цифрами.
В ней происходит вот что. Сначала, если a не было строкой, оно превращается в строку. Затем при помощи функции split разбивается на массив из отдельных цифр. То же происходит со вторым слагаемым — b. Затем вызывается функция res, которая и будет вычислять наш ответ. Поскольку число может быть как угодно длинное, то ответ мы будем собирать по одной цифре, в виде строки. Начальное значение строки-ответа "", на каждом рекурсивном вызове res мы будем вычислять по одной цифре.
Дальше вызывается функция res с начальными параметрами, запускает рекурсию.
Теперь по функции res: данная функция как раз и производит сложение. Практически обыкновенное, привычное школьное сложение в столбик.

Если немного переименовать параметры:
function res(a, b, result, carry) {
У нас слагаемые a и b, промежуточный результат в result, перенос из предыдущего разряда в carry
Если и левое, и правое слагаемое пустое, и нет переноса, то результат готов, его и возвращаем.
if(a.length == 0 && b.length == 0 && !carry) return result;
Вынесем сложные выражения в локальную переменную для простоты. Мы собираемся получить младшую цифру каждого из слагаемых, и убрать эту цифру из дальнейшего рассмотрения. Для этого мы пользуемся функцией pop, которая убирает последний элемент массива, отдаёт нам его.
var left = parseInt(a.pop() || '0', 10); var right = parseInt(b.pop() || '0',10);
То есть, для массива ['9', '8', '7'] функция pop() вернёт '7', а от массива останется лишь ['9', '8']
Если массив на самом деле был пустой, функция вернёт undefined. Тут-то нам и пригодится трюк с || '0': если результат был цифрой, она при этом не испортится, а вот undefined превратится в '0'!
Полученную цифру-строку мы превратили в число при помощи parseInt
Дальше мы складываем левую и правую цифры, и не забываем добавить перенос:
var l = left + right + (carry || 0);
Если перенос не указан, при помощи того же трюка превращаем его в 0
Осталось вызвать функцию рекурсивно, чтобы она провела ту же операцию со старшими разрядами. Только нужно пересчитать новый перенос:
return res(a, b, l + (result || ""), l > 9? 1:0); }
Но, как правильно заметил @Ni55aN, данная функция не всегда корректно работает.
Нужно немного изменить ее.
Добавить основание, например 10. Дело в том, что мы складываем по одной цифре. Но мы можем, по идее, и складывать большими кусками. Это была бы оптимизация. Затем, у нас баг: мы к результату добавляем часть, не «откусив» от неё перенесённый старший разряд. Это неправильно, надо убирать лишнее. Для случая двух слагаемых перенос не больше 1, но если мы захотим обобщить код на случай большего числа слагаемых, точное значение нужно будет вычислять.
Напишем точное вычисление «на вырост».
function res(a, b, result, carry, base) { if(a.length == 0 && b.length == 0 && !carry) return result;
//берем младшие разряды var left = parseInt(a.pop() || '0', 10); var right = parseInt(b.pop() || '0', 10);
//складываем и добавляем перебор с прошлой итерации var l = left + right + (carry || 0);
//вызываем для следующих разрядов, правильно вычисляя добавленную цифру и цифру переноса return res(a, b, l % base + (result || ""), Math.floor(l/base), base); }
function add(a, b) { return res(a.toString().split(""), b.toString().split(""), "","",10).toString(); }
Ещё одна мелочь: мы накапливаем результат в параметре, чтобы можно было вызвать функцию рекурсивно в конце самой функции. Это так называемая хвостовая рекурсия, её многие компиляторы умеют эффективно обрабатывать, не занимая стек.
Пример:
$(function() { $('#left,#right').change(function(){ var left = $('#left').val().trim(); var right = $('#right').val().trim(); console.log(left,right,isNaN(left),isNaN(right)); if(isNaN(left) || isNaN(right)) return; $('#sum').html(add(left,right)); }); function res(a, b, result, carry, base) { if (a.length == 0 && b.length == 0 && !carry) return result; //берем младшие разряды var left = parseInt(a.pop() || '0', 10); var right = parseInt(b.pop() || '0', 10); //складываем и добавляем перебор с прошлой итерации var l = left + right + (carry || 0); //вызываем для следующих разрядов return res(a, b, l % base + (result || ""), Math.floor(l / base), base); } function add(a, b) { return res(a.toString().split(""), b.toString().split(""), "", "", 10).toString(); } }); left:
right:
sum: