доказательство правильности этого рекурсивного алгоритма с использованием индукции

Question

int sumHelper(int n, int a) {
   if (n==0) return a;
   else return sumHelper(n-1, a + n*n);
}

int sumSqr(int n) { 
    return sumHelper(n, 0); 
}

Ребята, я должен доказать этот фрагмент кода, который использует хвостовую рекурсию для суммирования квадрата чисел. т.е. докажите, что при n ≥ 1 sumsqr (n) = 1 ^ 2 + 2 ^ 2 + ... n ^ 2. Я выяснил базовый случай, но я застрял на шаге индукции. Любые советы или помощь будут оценены.

Answer 1

Это работает для базового случая, как вы доказали. Представь себе, что это работает. Предположим, что это работает для n + 1. Как это работает для n, если n == 0, мы получаем всю сумму квадратов. Теперь мы можем подумать о дополнительных методах, которые были вызваны для n + 1. И это будет только первый, вернуть sumHelper (n, a + (n + 1) ^ 2). Все остальные методы будут выброшены так же, как в n. Итак, у нас есть a = сумма квадратов от 1 до n и (n + 1) ^ 2, так что, очевидно, это работает так, как вы предсказывали.