Избегание переполнения стека при рекурсивном добавлении номеров

Question

У меня есть рекурсивная функция, которая добавляет значение number к первому рекурсивному вызову, добавляет number-1 к второму рекурсивному вызову и так далее, пока не достигнет 0. Я реализовал эту функцию как:

public static int func(int number, int retval=0) 
{ 
    if (number<=0) 
     return retval; 
    return func(number-1, retval+number); 
} 

Как я могу написать это без создания переполнения стека, когда он вызывается с большим значением number? Нужен ли мне отдельный файл?

Answer 1

В первом рекурсивном обращении вы добавляете number, во втором добавляете number-1 и так далее, пока вы, наконец, не добавите 0 и не прекратите рекурсию. Поэтому это эквивалентно только возврату retval + number + (number-1) + ... + 1, which is equal toretval + (number+1)*number/2.

Таким образом, вы можете избежать рекурсии полностью (и потенциал переполнения стека), заменив вашу функцию с:

public static int func(int number, int retval=0) 
{ 
    if (number<=0) { 
     return retval; 
    } else { 
     return retval + (number+1)*number/2; 
    } 
} 

Дополнительное преимущество этого подхода заключается в том, что он работает в O(1) время, в то время как рекурсивный подход от вашего вопроса и его итеративный экземпляр выполняются в режиме O(number).

Answer 2

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

Для вашей функции:

public static int func(int number, int retval=0) 
{ 
    if (number<=0) 
     return retval; 
    return func(number-1, retval+number); 
} 

Это будет выглядеть следующим образом:

public static int func(int number, int retval=0) 
{ 
top: 
    if (number<=0) 
     return retval; 
    //return func(number-1, retval+number); 
    number = number - 1; 
    retval = retval + number; 
    goto top; 
} 

Чтобы избавиться от уродливых goto вы можете заменить с while цикла (так как условие выхода находится на Вверх).

Теперь функция выглядит так:

public static int func(int number, int retval=0) 
{ 
    while (! number<=0) 
    { 
    number = number - 1; 
    retval = retval + number; 
    } 
    return retval; 
} 

Это уже не рекурсивная и не может вызвать переполнение стека.

Answer 3

Если вы должны использовать рекурсию добавить целое число в вашей функции, которая содержит оставшиеся «пространство» в стеке, что-то вроде:

public static int func(int number, int retval=0, int numberOfCalls) 
{ 
    if(numberOfCalls >= maximumBeforeStackOverflow) 
    { 
     //throw exception you can catch (you can't cath stackoverflow if i'm correct) 
     //or break func 
    } 
    if (number<=0) 
    { 
     return retval; 
    } 
    return func(number-1, retval+number, numberOfCalls++); 
}