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

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. Я выяснил базовый вариант, но застрял на этапе индукции. Мы будем благодарны за любые подсказки или помощь.


java recursion induction
person Manny    schedule 15.05.2018    source источник
comment
Это чисто математический вопрос. Я бы проголосовал за это как не по теме. Да, код есть, но код - это просто реализация математического алгоритма.   -  person Ben    schedule 15.05.2018
comment
Я думаю, что это могло бы быть более подходящим для одной из бирж стека информатики.   -  person Mark Rotteveel    schedule 15.05.2018

Ответы (1)


arrow_upward
0
arrow_downward

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

person Ajris    schedule 15.05.2018