Решение рекурсивного алгоритма методом итерации

Question

Рассмотрим следующий рекурсивный алгоритм вычисления суммы первых n квадратов. Сумма (n) = 1square + 2square + ....... n square. Алгоритм:

int Sum (n) { 
    if (n=1) return 1 ; 
    else return sum (n-1)+n*n; 
} 

Написать соотношение для вышеприведенного алгоритма и решить методом итераций.

Answer 1

Подумайте о замене call sum(n-1) на (n-1)*(n-1) на номер n = n-1 и так далее. Так что ваш итерационный алго должно быть что-то вроде:

sum = 0 
for (i from 1 to n) 
do 
    sum += i*i 
done 

Answer 2

#include<stdio.h> 
int add(int n); 
int main() 
    { 
    int n; 
    printf("Enter an positive integer: "); 
    scanf("%d",&n); 
    printf("Sum = %d",sumofsquare(n)); 
    return 0; 
} 
int sumofsquare(int n) 
{ 
if(n>1) 
return n*n+sumofsquare(n-1); /* recursive call */ 
else if (n==1) 
return 1; 
    }