Переполнение стека вызывает ошибку времени исполнения

Переполнение стека

  • Определение
  • Стек программы
  • Последствия ошибки
  • Причины ошибки
  • Примеры
  • Итог
  • Библиографический список

Определение

Переполнение стека — программная ошибка времени выполнения, при которой программа захватывает всю память, выделенную ей под стек, что обычно приводит к аварийному завершению её работы.

Стек программы

Стек программы — это специальная области памяти, организованная по принципу очереди LIFO (Last in, first out — последним пришел, первым ушел). Название «стек» произошло из-за аналогии принципа его построения со стопкой (англ. stack) тарелок — можно класть тарелки друг на друга (метод добавления в стек, «заталкивание», «push»), а затем забирать их, начиная с верхней (метод получения значения из стека, «выталкивание», «pop»). Стек программы также называют стек вызовов, стек выполнения, машинным стеком (чтобы не путать его со «стеком» — абстрактной структурой данных).

Для чего нужен стек? Он позволяет удобно организовать вызов подпрограмм. При вызове функция получает некоторые аргументы; также она должна где-то хранить свои локальные переменные. Кроме того, надо учесть, что одна функция может вызвать другую функцию, которой тоже надо передавать параметры и хранить свои переменные. Используя стек, при передаче параметров нужно просто положить их в стек, тогда вызываемая функция сможет их оттуда «вытолкнуть» и использовать. Локальные переменные тоже можно хранить там же — в начале своего кода функция выделяет часть памяти стека, при возврате управления — очищает и освобождает. Программисты на высокоуровневых языках обычно не задумываются о таких вещах — весь необходимый рутинный код за них генерирует компилятор.

Последствия ошибки

Теперь мы подошли почти вплотную к проблеме. В абстрактном виде стек представляет собой бесконечное хранилище, в которое можно бесконечно добавлять новые элементы. К сожалению, в нашем мире все конечно — и память под стек не исключение. Что будет, если она закончится, когда в стек заталкиваются аргументы функции? Или функция выделяет память под свои переменные?

Произойдет ошибка, называемая переполнением стека. Поскольку стек необходим для организации вызова пользовательских функций (а практически все программы на современных языках, в том числе объектно-ориентированных, так или иначе строятся на основе функций), больше они вызываться не смогут. Поэтому операционная система забирает управление, очищает стек и завершает программу. Здесь можно подчеркнуть различие между переполнением буфера и переполнением стека — в первом случае ошибка происходит при обращении к неверной области памяти, и если защита на этом этапе отсутствует, в этот момент не проявляет себя — при удачном стечении обстоятельств программа может отработать нормально. Если только память, к которой шло обращение, была защищена, происходит ошибка сегментации. В случае со стеком программа непременно завершается.

Чтобы быть совсем точным, следует отметить, что подобное описание событий верно лишь для компиляторов, компилирующих в «родной» (native) код. В управляемых языках у виртуальной машины есть свой стек для управляемых программ, за состоянием которого гораздо проще следить, и можно даже позволить себе при возникновении переполнения передать программе исключение. В языках Си и Си++ на подобную «роскошь» рассчитывать не приходится.

Причины ошибки

Что же может привести к такой неприятной ситуации? Исходя из описанного выше механизма, один из вариантов — слишком большое число вложенных вызовов функций. Особенно вероятен такой вариант развития событий при использовании рекурсии. Бесконечная рекурсия (при отсутствии механизма «ленивых» вычислений) прерывается именно таким образом, в отличие от бесконечного цикла, который иногда имеет полезное применение. Впрочем, при небольшом объеме памяти, отведенной под стек (что, например, характерно для микроконтроллеров), достаточно может быть и простой последовательности вызовов.

Другой вариант — локальные переменные, требующие большого количества памяти. Заводить локальный массив из миллиона элементов, или миллион локальных переменных (мало ли что бывает) — не самая лучшая идея. Даже один вызов такой «жадной» функции легко может вызвать переполнение стека. Для получения больших объемов данных лучше воспользоваться механизмами динамической памяти, которая позволит обработать ошибку её нехватки.

Однако динамическая память является довольно медленной в плане выделения и освобождения (поскольку этим занимается операционная система), кроме того, при прямом доступе приходится вручную выделять её и освобождать. Память же в стеке выделяется очень быстро (по сути, надо лишь изменить значение одного регистра), кроме того, у объектов, выделенных в стеке, автоматически вызываются деструкторы при возврате управления функцией и очистке стека. Разумеется, тут же возникает желание получить память из стека. Поэтому третий путь к переполнению — самостоятельное выделение в стеке памяти программистом. Специально для этой цели библиотека языка Си предоставляет функцию alloca. Интересно заметить, что если у функции для выделения динамической памяти malloc есть свой «близнец» для её освобождения free, то у функции alloca его нет — память освобождается автоматически после возврата управления функцией. Возможно, это только осложняет ситуацию — ведь до выхода из функции освободить память не получится. Даже несмотря на то, что согласно man-странице «функция alloca зависит от машины и компилятора; во многих системах ее реализация проблематична и содержит много ошибок; ее использование очень несерьезно и не одобряется» — она все равно используется.

Примеры

В качестве примера рассмотрим код для рекурсивного поиска файлов, расположенный на MSDN:

void DirSearch(String* sDir)
 {
     try
     {
         // Find the subfolders in the folder that is passed in.
         String* d[] = Directory::GetDirectories(sDir);
         int numDirs = d->get_Length();
         
         for (int i=0; i < numDirs; i++)
         {
             // Find all the files in the subfolder.
             String* f[] = Directory::GetFiles(d[i],textBox1->Text);
             int numFiles = f->get_Length();

             for (int j=0; j < numFiles; j++)
             {
                 listBox1->Items->Add(f[j]);
             }
             DirSearch(d[i]);
         }
     }
     catch (System::Exception* e)
     {
         MessageBox::Show(e->Message);
     }
 }

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

Пример второго подхода, взятый из вопроса «Почему происходит переполнение стека?» с сайта под названием Stack Overflow (сайт является сборником вопросов и ответов на любые программистские темы, а не только по переполнению стека, как может показаться):

#define W 1000
#define H 1000
#define MAX 100000 
//...
int main()
{
    int image[W*H];
    float dtr[W*H];
    initImg(image,dtr);
    return 0;
}

Как видно, в функции main выделяется память в стеке под массивы типов int и float по миллиону элементов каждый, что в сумме дает чуть менее 8 мегабайт. Если учесть, что по умолчанию Visual C++ резервирует под стек лишь 1 мегабайт, то ответ становится очевидным.

А вот пример, взятый из GitHub-репозитория проекта Flash-плеера Lightspark:

DefineSoundTag::DefineSoundTag(/* ... */)
{
    // ...
    unsigned int soundDataLength = h.getLength()-7;
    unsigned char *tmp = (unsigned char *)alloca(soundDataLength);
    // ...
}

Можно надеятся, что h.getLength()-7 не будет слишком большим числом, чтобы на следующей строчке не произошло переполнения. Но стоит ли сэкономленное на выделении памяти время «потенциального» вылета программы?

Итог

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

Библиографический список

  • Э. Таненбаум. Архитектура компьютера.
  • Wikipedia. Stack Overflow.
  • man 3 alloca.
  • MSDN. How to recursively search folders by using Visual C++.
  • Stack Overflow. Stack Overflow C++.
  • GitHub. Lightspark — «tags.cpp».

Присылаем лучшие статьи раз в месяц

To describe this, first let us understand how local variables and objects are stored.

Local variable are stored on the stack:

Enter image description here

If you looked at the image you should be able to understand how things are working.

When a function call is invoked by a Java application, a stack frame is allocated on the call stack. The stack frame contains the parameters of the invoked method, its local parameters, and the return address of the method. The return address denotes the execution point from which, the program execution shall continue after the invoked method returns. If there is no space for a new stack frame then, the StackOverflowError is thrown by the Java Virtual Machine (JVM).

The most common case that can possibly exhaust a Java application’s stack is recursion. In recursion, a method invokes itself during its execution. Recursion is considered as a powerful general-purpose programming technique, but it must be used with caution, to avoid StackOverflowError.

An example of throwing a StackOverflowError is shown below:

StackOverflowErrorExample.java:

public class StackOverflowErrorExample {

    public static void recursivePrint(int num) {
        System.out.println("Number: " + num);
        if (num == 0)
            return;
        else
            recursivePrint(++num);
        }

    public static void main(String[] args) {
        StackOverflowErrorExample.recursivePrint(1);
    }
}

In this example, we define a recursive method, called recursivePrint that prints an integer and then, calls itself, with the next successive integer as an argument. The recursion ends until we pass in 0 as a parameter. However, in our example, we passed in the parameter from 1 and its increasing followers, consequently, the recursion will never terminate.

A sample execution, using the -Xss1M flag that specifies the size of the thread stack to equal to 1 MB, is shown below:

Number: 1
Number: 2
Number: 3
...
Number: 6262
Number: 6263
Number: 6264
Number: 6265
Number: 6266
Exception in thread "main" java.lang.StackOverflowError
        at java.io.PrintStream.write(PrintStream.java:480)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        at java.io.PrintStream.print(PrintStream.java:669)
        at java.io.PrintStream.println(PrintStream.java:806)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:4)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        ...

Depending on the JVM’s initial configuration, the results may differ, but eventually the StackOverflowError shall be thrown. This example is a very good example of how recursion can cause problems, if not implemented with caution.

How to deal with the StackOverflowError

  1. The simplest solution is to carefully inspect the stack trace and
    detect the repeating pattern of line numbers. These line numbers
    indicate the code being recursively called. Once you detect these
    lines, you must carefully inspect your code and understand why the
    recursion never terminates.

  2. If you have verified that the recursion
    is implemented correctly, you can increase the stack’s size, in
    order to allow a larger number of invocations. Depending on the Java
    Virtual Machine (JVM) installed, the default thread stack size may
    equal to either 512 KB, or 1 MB. You can increase the thread stack
    size using the -Xss flag. This flag can be specified either via the
    project’s configuration, or via the command line. The format of the
    -Xss argument is:
    -Xss<size>[g|G|m|M|k|K]

To describe this, first let us understand how local variables and objects are stored.

Local variable are stored on the stack:

Enter image description here

If you looked at the image you should be able to understand how things are working.

When a function call is invoked by a Java application, a stack frame is allocated on the call stack. The stack frame contains the parameters of the invoked method, its local parameters, and the return address of the method. The return address denotes the execution point from which, the program execution shall continue after the invoked method returns. If there is no space for a new stack frame then, the StackOverflowError is thrown by the Java Virtual Machine (JVM).

The most common case that can possibly exhaust a Java application’s stack is recursion. In recursion, a method invokes itself during its execution. Recursion is considered as a powerful general-purpose programming technique, but it must be used with caution, to avoid StackOverflowError.

An example of throwing a StackOverflowError is shown below:

StackOverflowErrorExample.java:

public class StackOverflowErrorExample {

    public static void recursivePrint(int num) {
        System.out.println("Number: " + num);
        if (num == 0)
            return;
        else
            recursivePrint(++num);
        }

    public static void main(String[] args) {
        StackOverflowErrorExample.recursivePrint(1);
    }
}

In this example, we define a recursive method, called recursivePrint that prints an integer and then, calls itself, with the next successive integer as an argument. The recursion ends until we pass in 0 as a parameter. However, in our example, we passed in the parameter from 1 and its increasing followers, consequently, the recursion will never terminate.

A sample execution, using the -Xss1M flag that specifies the size of the thread stack to equal to 1 MB, is shown below:

Number: 1
Number: 2
Number: 3
...
Number: 6262
Number: 6263
Number: 6264
Number: 6265
Number: 6266
Exception in thread "main" java.lang.StackOverflowError
        at java.io.PrintStream.write(PrintStream.java:480)
        at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
        at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
        at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
        at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
        at java.io.PrintStream.write(PrintStream.java:527)
        at java.io.PrintStream.print(PrintStream.java:669)
        at java.io.PrintStream.println(PrintStream.java:806)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:4)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        at StackOverflowErrorExample.recursivePrint(StackOverflowErrorExample.java:9)
        ...

Depending on the JVM’s initial configuration, the results may differ, but eventually the StackOverflowError shall be thrown. This example is a very good example of how recursion can cause problems, if not implemented with caution.

How to deal with the StackOverflowError

  1. The simplest solution is to carefully inspect the stack trace and
    detect the repeating pattern of line numbers. These line numbers
    indicate the code being recursively called. Once you detect these
    lines, you must carefully inspect your code and understand why the
    recursion never terminates.

  2. If you have verified that the recursion
    is implemented correctly, you can increase the stack’s size, in
    order to allow a larger number of invocations. Depending on the Java
    Virtual Machine (JVM) installed, the default thread stack size may
    equal to either 512 KB, or 1 MB. You can increase the thread stack
    size using the -Xss flag. This flag can be specified either via the
    project’s configuration, or via the command line. The format of the
    -Xss argument is:
    -Xss<size>[g|G|m|M|k|K]

В мире программистов ошибка «stack overflow» очень известна благодаря тому, что этот вид ошибки довольно распространен. А сам термин «stack overflow» известен еще больше, чем ошибка, благодаря одноименному англоязычному ресурсу «StackOverflow». Это сообщество программистов международного масштаба, и еще куча всего интересного. Поэтому не нужно путать ошибку «stack overflow» и веб-ресурс с таким же названием. В нашей статье речь пойдет об ошибке.

Ошибка «stack overflow» связана с переполнением стека. Она появляется в том случае, когда в стеке должно сохраниться больше информации, чем он может уместить. Объем памяти стека задает программист при запуске программы. Если в процессе выполнения программы стек переполняется, тогда возникает ошибка «stack overflow» и программа аварийно завершает работу. Причин возникновения подобной ошибки может быть несколько.

Ошибка «stack overflow»

Нужно отметить, что ошибка «stack overflow» не связана с конкретным языком программирования, то есть она может возникнуть в программах на Java, C++, C, C# и других компилируемых языках.

Причин ее возникновения может быть несколько. К самым распространенным причинам относятся:

  • бесконечная рекурсия;

  • глубокая рекурсия;

  • проблемы с переменными в стеке.

Бесконечная рекурсия и ошибка «stack overflow» 

Бесконечная рекурсия редко возникает самостоятельно и по неизвестным причинам. Обычно программист:

  • забывает прописывать условие для выхода из рекурсии;

  • пишет неосознанную косвенную рекурсию.

Самая частая причина из категории «бесконечной рекурсии» — программист забывает прописывать условия выхода или же прописывает, но условия выхода не срабатывают.

Вот как это выглядит на С:

int factorial (int number)

{

  if (number == 0)

    return 1;

  return number * factorial(number — 1);

}

В описанном примере прописаны условия выхода из рекурсии, однако они никогда не сработают, если «number» будет отрицательным. Поэтому через несколько миллионов вызовов стек будет переполнен и возникнет ошибка «stack overflow». В некоторых языках программирования предусмотрена «защита» от таких рекурсий. В них рекурсия из конца функции конвертируется в цикл, что не будет расходовать стековую память. Но подобная «оптимизация» вызовет другую, менее опасную проблему — «зацикливание».

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

В коде это выглядит так:

 int Object::getNumber(int index, bool& isChangeable)

{

  isChangeable = true;

  return getNumber(index);

}

int Object::getNumber(int index)

{

  bool noValue;

  return getNumber(index, noValue);

}

Глубокая рекурсия и ошибка «stack overflow»

Глубокая рекурсия — это такая рекурсия, которая имеет свое окончание через определенное время, поэтому она не бесконечная. Однако памяти стека не хватит для завершения такой рекурсии, поэтому ошибка «stack overflow» обеспечена. Обычно такая ситуация заранее просчитывается программистом,поэтому ее можно решить. Например, можно:

  • отыскать другой программный алгоритм для решения поставленной задачи, чтобы избежать применения рекурсии;

  • «вынести» рекурсию за пределы аппаратного стека в динамический;

  • и другое.

Глубокая рекурсия выглядит так:

void eliminateList(struct Item* that)

{

    if (that == NULL)

        return;

    eliminateList(that->next);

    free(that);

}

Проблемы с переменными в стеке и ошибка «stack overflow»

Если взглянуть на популярность возникновения «stack overflow error», то причина с проблемными переменными в стеке стоит на первом месте. Кроется она в том, что программист изначально выделяет слишком много памяти локальной переменной.

Например:

int function() {

     double b[1000000]

}

В данном случае может возникнуть такая ситуация, что массиву потребуется объем памяти, который стек не способен будет обеспечить, а значит, возникнет ошибка «stack overflow». 

Заключение

Ошибка «stack overflow» возникает довольно часто. Каждый конкретный случай ее возникновения требует собственного решения. Одна причина объединяет возникновение такой ошибки — невнимательность программиста. Если «stack overflow error» возникла, значит, программист где-то что-то упустил или не доглядел.

Что означает ошибка Uncaught RangeError: Maximum call stack size exceeded

Что означает ошибка Uncaught RangeError: Maximum call stack size exceeded

Это когда вызывается слишком много вложенных функций

Это когда вызывается слишком много вложенных функций

Ситуация: заказчик попросил разместить на странице кликабельную картинку, а чтобы на неё обратило внимание больше посетителей, попросил сделать вокруг неё моргающую рамку. Логика моргания в скрипте очень простая:

  1. В первой функции находим на странице нужный элемент.
  2. Добавляем рамку с какой-то задержкой (чтобы она какое-то время была на экране).
  3. Вызываем функцию убирания рамки.
  4. Внутри второй функции находим тот же элемент на странице.
  5. Убираем рамку с задержкой.
  6. Вызываем первую функцию добавления рамки.

Код простой, поэтому делаем всё в одном файле:

<!DOCTYPE html>
<html>
<head>
	<meta charset="utf-8">
	<meta name="viewport" content="width=device-width, initial-scale=1">
	<title>Pulse</title>
	<style type="text/css">
	/*	рамка, которая будет моргать	*/
		.pulse { box-shadow: 0px 0px 4px 4px #AEA79F; }
	</style>
</head>
<body>
	<div id="pulseDiv"> 
    	<a href="#">
      		<div id="advisersDiv">
        		<img src="https://thecode.media/wp-content/uploads/2020/08/photo_2020-08-05-12.04.57.jpeg">
        	</div>
      	</a>
</div>
<!-- подключаем jQuery -->
<script src="https://yastatic.net/jquery/3.3.1/jquery.min.js" type="text/javascript"></script>
<!-- наш скрипт -->
<script type="text/javascript">
	// добавляем рамку
	function fadeIn() {
		// находим нужный элемент и добавляем рамку с задержкой
  	$('#pulseDiv').find('div#advisersDiv').delay(400).addClass("pulse");
  	// затем убираем рамку
  	fadeOut();
	};
	// убираем рамку
	function fadeOut() {
		// находим нужный элемент и убираем рамку с задержкой
   	$('#pulseDiv').find('div#advisersDiv').delay(400).removeClass("pulse");
   	// затем добавляем 
   	fadeIn();
	};
	// запускаем моргание рамки
	fadeIn();
</script>

</body>
</html>

Но при открытии страницы в браузере мы видим, что ничего не моргает, а в консоли появилась ошибка:

❌ Uncaught RangeError: Maximum call stack size exceeded

Что это значит: в браузере произошло переполнение стека вызовов и из-за этого он не может больше выполнять этот скрипт.

Переполнения стека простыми словами означает вот что:

  1. Когда компьютер что-то делает, он это делает последовательно — 1, 2, 3, 4.
  2. Иногда ему нужно отвлечься от одного и сходить сделать что-то другое — а, б, в, г, д. Получается что-то вроде 1, 2, 3 → а, б, в, г, д → 4.
  3. Вот эти переходы 3 → а и д → 4 — это компьютеру нужно запомнить, что он выполнял пункт 3, и потом к нему вернуться.
  4. Каждое запоминание, что компьютер бросил и куда ему нужно вернуться, — это называется «вызов».
  5. Вызовы хранятся в стеке вызовов. Это стопка таких ссылок типа «когда закончишь вот это, вернись туда».
  6. Стек не резиновый и может переполняться.

Что делать с ошибкой Uncaught RangeError: Maximum call stack size exceeded

Эта ошибка — классическая ошибка переполнения стека во время выполнения рекурсивных функций.

Рекурсия — это когда мы вызываем функцию внутри самой себя, но чуть с другими параметрами. Когда параметр дойдёт до конечного значения, цепочка разматывается обратно и функция собирает вместе все значения. Это удобно, когда у нас есть чёткий алгоритм подсчёта с понятными правилами вычислений.

В нашем случае рекурсия возникает, когда в конце обеих функций мы вызываем другую: 

  1. Функции начинают бесконтрольно вызывать себя бесконечное число раз.
  2. Стек вызовов начинает запоминать вызов каждой функции, чтобы, когда она закончится, вернуться к тому, что было раньше.
  3. Стек — это определённая область памяти, у которой есть свой объём.
  4. Вызовы не заканчиваются, и стек переполняется — в него больше нельзя записать вызов новой функции, чтобы потом вернуться обратно.
  5. Браузер видит всё это безобразие и останавливает скрипт.

То же самое будет, если мы попробуем запустить простую рекурсию слишком много раз:

Что означает ошибка Uncaught RangeError: Maximum call stack size exceeded

Как исправить ошибку Uncaught RangeError: Maximum call stack size exceeded

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

В нашем случае проблема возникает из-за того, что мы вызывали вторые функции бесконтрольно, поэтому они множились без ограничений. Решение — ограничить вызов функции одной секундой — так они будут убираться из стека и переполнения не произойдёт:

<script type="text/javascript">
// добавляем рамку
function fadeIn() {
	// находим нужный элемент и добавляем рамку с задержкой
	$('#pulseDiv').find('div#advisersDiv').delay(400).addClass("pulse");
	// через секунду убираем рамку
	setTimeout(fadeOut,1000)
};
// убираем рамку
function fadeOut() {
	// находим нужный элемент и убираем рамку с задержкой
 	$('#pulseDiv').find('div#advisersDiv').delay(400).removeClass("pulse");
 	// через секунду добавляем рамку
	setTimeout(fadeIn,1000)
};
// запускаем моргание рамки
fadeIn();
</script>

Что означает ошибка Uncaught RangeError: Maximum call stack size exceeded

Вёрстка:

Кирилл Климентьев

Получите ИТ-профессию

В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.

Начать карьеру в ИТ

Получите ИТ-профессию
Получите ИТ-профессию
Получите ИТ-профессию
Получите ИТ-профессию

serjufa1

1 / 1 / 0

Регистрация: 15.10.2007

Сообщений: 83

1

27.02.2021, 14:38. Показов 2862. Ответов 4

Метки нет (Все метки)

здравствуйте.
Выходит ошибка «Ошибка времени выполнения: StackOverflowException: Программа завершена из-за переполнения программного стека
«
Вот задача
(Е. Джобс) Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n + 1 при n < 3,
F(n) = n + 2*F(n + 2), когда n ≥ 3 и четно,
F(n) = F(n – 2) + n – 2, когда n ≥ 3 и нечетно.
Сколько существует чисел n, для которых значение F(n) будет трехзначным

ВОТ РЕШЕНИЕ

PureBasic 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//Функция F
function F(n: integer): integer;
begin
  if n < 3 then 
    F := n + 1;  
  if (n >= 3) and (n mod 2 = 0) then
    F := n + 2 * F(n + 2);
  if (n >= 3) and (n mod 2 <> 0) then
    F := n + 2 * F(n + 2);  
  
end;
 
var
  cikl, kolvo: integer;
//Основная часть программы, где запускаем функцию.
begin
  kolvo := 0;
  for cikl := 1 to 1000 do
  begin
    if (F(cikl) >= 100) and (F(cikl) <= 999) then
      kolvo := kolvo + 1; 
  end;
  
  WriteLn(cikl);
end.

__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь

0

Programming

Эксперт

94731 / 64177 / 26122

Регистрация: 12.04.2006

Сообщений: 116,782

 27.02.2021, 14:38

4

canadamoscow

1045 / 404 / 187

Регистрация: 23.03.2020

Сообщений: 980

Записей в блоге: 1

27.02.2021, 16:37

2
Pascal 
1
2
3
4
5
6
7
8
9
10
11
12

function F(n: integer): integer;
begin
  if n < 3 then  F := n + 1
  else if odd(n) then F := F(n-2) + n-2
end;
 
begin
  var kolvo := 0;
  for var n := -2000 to 2000 do  
    if (abs(f(n)) >= 100) and (abs(f(n)) < 1000) then inc(kolvo);
  Writeln(kolvo);
end.

0

serjufa1

1 / 1 / 0

Регистрация: 15.10.2007

Сообщений: 83

27.02.2021, 20:25

 [ТС]

3

Прошу прощения, я неправильно указал часть кода.
Сейчас поправил код. Теперь он совпадает с заданием. Но, ошибка осталась.
Наверное, Ваш ответ тоже изменится.

PureBasic 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//Функция F
function F(n: integer): integer;
begin
  if n < 3 then 
    F := n + 1
    else
  if ((n mod 2) = 0) then
    F := n + 2 * F(n + 2)
  else
         F := F(n - 2) + n - 2;   
end;
 
var
  cikl, kolvo: integer;
//Основная часть программы, где запускаем функцию.
begin
  kolvo := 0;
  for cikl := 1 to 100 do
  begin
    if (F(cikl) >= 100) and (F(cikl) <= 999) then
      kolvo := kolvo + 1; 
  end;
  
  WriteLn(cikl);
end.

Также я не понял мысль про

PureBasic 
1

for var n := -2000 to 2000 do

0

2109 / 1258 / 476

Регистрация: 07.04.2017

Сообщений: 4,444

27.02.2021, 20:57

4

Цитата
Сообщение от serjufa1
Посмотреть сообщение

F(n) = n + 2*F(n + 2)

Это принципиально не будет работать. Для того чтоб посчитать F(n) вам надо посчитать F(n+2). n+2 тоже будет чётным, раз n чётно. А значит чтоб посчитать F(n+2) — надо сначала посчитать F(n+4). И так до бесконечности.

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

Выясняйте у преподавателя, потому что задание неправильное.

1

2801 / 1480 / 594

Регистрация: 19.03.2019

Сообщений: 4,904

01.03.2021, 12:31

5

Цитата
Сообщение от Sun Serega
Посмотреть сообщение

Это принципиально не будет работать. Для того чтоб посчитать F(n) вам надо посчитать F(n+2). n+2 тоже будет чётным, раз n чётно. А значит чтоб посчитать F(n+2) — надо сначала посчитать F(n+4). И так до бесконечности.

Абсолютно согласен.

Это очередная кривая задача из сборника задач Полякова.

Цитата
Сообщение от Иванин
Посмотреть сообщение

Эта задача №67

Ошибка времени выполнения: StackOverflowException: Программа завершена из-за переполнения программного стека

Решения, как и некоторые другие (см. обсуждение здесь — Не могу найти ошибку!) НЕ ИМЕЕТ.

0
Источник

I have a problem when use recursive method call.
I know the problem here setInfo(ref name, ref age, ref address, ref country);, but I don’t know how to fix it.

class person{
        private string name;
        private short age;
        private string address;
        private string country;

        public person(){
            Console.Write("Hi i'm constructor nn");
        }

        public void setInfo(ref string name, ref short age, ref string address, ref string country){
            if (name != "" || address != "" || country != "" || age != 0) {
                this.name = name;
                this.age = age;
                this.address = address;
                this.country = country;
            } else {
                setInfo(ref name, ref age, ref address, ref country); // Here is what I doubt.
            }
        }

        public void getInfo(){
            Console.Clear();
            Console.WriteLine("---- The information ----nName: {0}nAge: {1}nAddress: {2}nCountry: {3}", this.name, this.age, this.address, this.country);
        }

    }


// When usage


static void Main(string[] args){
            string name, address, country;
            short age; 

            person one = new person();

            Console.Write("Name: ");
            name = Console.ReadLine();

            Console.Write("Age: ");
            Int16.TryParse(Console.ReadLine(), out age);

            Console.Write("Address: ");
            address = Console.ReadLine();

            Console.Write("Country: ");
            country = Console.ReadLine();

            one.setInfo(ref name, ref age, ref address, ref country);
            one.getInfo();
        }

Источник

serjufa1

1 / 1 / 0

Регистрация: 15.10.2007

Сообщений: 83

1

27.02.2021, 14:38. Показов 4467. Ответов 4

Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам

здравствуйте.
Выходит ошибка «Ошибка времени выполнения: StackOverflowException: Программа завершена из-за переполнения программного стека
«
Вот задача
(Е. Джобс) Алгоритм вычисления функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n + 1 при n < 3,
F(n) = n + 2*F(n + 2), когда n ≥ 3 и четно,
F(n) = F(n – 2) + n – 2, когда n ≥ 3 и нечетно.
Сколько существует чисел n, для которых значение F(n) будет трехзначным

ВОТ РЕШЕНИЕ

PureBasic 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//Функция F
function F(n: integer): integer;
begin
  if n < 3 then 
    F := n + 1;  
  if (n >= 3) and (n mod 2 = 0) then
    F := n + 2 * F(n + 2);
  if (n >= 3) and (n mod 2 <> 0) then
    F := n + 2 * F(n + 2);  
  
end;
 
var
  cikl, kolvo: integer;
//Основная часть программы, где запускаем функцию.
begin
  kolvo := 0;
  for cikl := 1 to 1000 do
  begin
    if (F(cikl) >= 100) and (F(cikl) <= 999) then
      kolvo := kolvo + 1; 
  end;
  
  WriteLn(cikl);
end.



0

Programming

Эксперт

94731 / 64177 / 26122

Регистрация: 12.04.2006

Сообщений: 116,782

 27.02.2021, 14:38

4

canadamoscow

1054 / 409 / 190

Регистрация: 23.03.2020

Сообщений: 989

Записей в блоге: 1

27.02.2021, 16:37

2
Pascal 
1
2
3
4
5
6
7
8
9
10
11
12

function F(n: integer): integer;
begin
  if n < 3 then  F := n + 1
  else if odd(n) then F := F(n-2) + n-2
end;
 
begin
  var kolvo := 0;
  for var n := -2000 to 2000 do  
    if (abs(f(n)) >= 100) and (abs(f(n)) < 1000) then inc(kolvo);
  Writeln(kolvo);
end.



0

serjufa1

1 / 1 / 0

Регистрация: 15.10.2007

Сообщений: 83

27.02.2021, 20:25

 [ТС]

3

Прошу прощения, я неправильно указал часть кода.
Сейчас поправил код. Теперь он совпадает с заданием. Но, ошибка осталась.
Наверное, Ваш ответ тоже изменится.

PureBasic 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

//Функция F
function F(n: integer): integer;
begin
  if n < 3 then 
    F := n + 1
    else
  if ((n mod 2) = 0) then
    F := n + 2 * F(n + 2)
  else
         F := F(n - 2) + n - 2;   
end;
 
var
  cikl, kolvo: integer;
//Основная часть программы, где запускаем функцию.
begin
  kolvo := 0;
  for cikl := 1 to 100 do
  begin
    if (F(cikl) >= 100) and (F(cikl) <= 999) then
      kolvo := kolvo + 1; 
  end;
  
  WriteLn(cikl);
end.

Также я не понял мысль про

PureBasic 
1

for var n := -2000 to 2000 do



0

2182 / 1310 / 498

Регистрация: 07.04.2017

Сообщений: 4,577

27.02.2021, 20:57

4

Цитата
Сообщение от serjufa1
Посмотреть сообщение

F(n) = n + 2*F(n + 2)

Это принципиально не будет работать. Для того чтоб посчитать F(n) вам надо посчитать F(n+2). n+2 тоже будет чётным, раз n чётно. А значит чтоб посчитать F(n+2) — надо сначала посчитать F(n+4). И так до бесконечности.

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

Выясняйте у преподавателя, потому что задание неправильное.



1

2909 / 1558 / 625

Регистрация: 19.03.2019

Сообщений: 5,158

01.03.2021, 12:31

5

Цитата
Сообщение от Sun Serega
Посмотреть сообщение

Это принципиально не будет работать. Для того чтоб посчитать F(n) вам надо посчитать F(n+2). n+2 тоже будет чётным, раз n чётно. А значит чтоб посчитать F(n+2) — надо сначала посчитать F(n+4). И так до бесконечности.

Абсолютно согласен.

Это очередная кривая задача из сборника задач Полякова.

Цитата
Сообщение от Иванин
Посмотреть сообщение

Эта задача №67

Ошибка времени выполнения: StackOverflowException: Программа завершена из-за переполнения программного стека

Решения, как и некоторые другие (см. обсуждение здесь — Не могу найти ошибку!) НЕ ИМЕЕТ.



0
Источник

В мире программистов ошибка «stack overflow» очень известна благодаря тому, что этот вид ошибки довольно распространен. А сам термин «stack overflow» известен еще больше, чем ошибка, благодаря одноименному англоязычному ресурсу «StackOverflow». Это сообщество программистов международного масштаба, и еще куча всего интересного. Поэтому не нужно путать ошибку «stack overflow» и веб-ресурс с таким же названием. В нашей статье речь пойдет об ошибке.

Ошибка «stack overflow» связана с переполнением стека. Она появляется в том случае, когда в стеке должно сохраниться больше информации, чем он может уместить. Объем памяти стека задает программист при запуске программы. Если в процессе выполнения программы стек переполняется, тогда возникает ошибка «stack overflow» и программа аварийно завершает работу. Причин возникновения подобной ошибки может быть несколько.

Ошибка «stack overflow»

Нужно отметить, что ошибка «stack overflow» не связана с конкретным языком программирования, то есть она может возникнуть в программах на Java, C++, C, C# и других компилируемых языках.

Причин ее возникновения может быть несколько. К самым распространенным причинам относятся:

  • бесконечная рекурсия;

  • глубокая рекурсия;

  • проблемы с переменными в стеке.

Бесконечная рекурсия и ошибка «stack overflow» 

Бесконечная рекурсия редко возникает самостоятельно и по неизвестным причинам. Обычно программист:

  • забывает прописывать условие для выхода из рекурсии;

  • пишет неосознанную косвенную рекурсию.

Самая частая причина из категории «бесконечной рекурсии» — программист забывает прописывать условия выхода или же прописывает, но условия выхода не срабатывают.

Вот как это выглядит на С:

int factorial (int number)

{

  if (number == 0)

    return 1;

  return number * factorial(number — 1);

}

В описанном примере прописаны условия выхода из рекурсии, однако они никогда не сработают, если «number» будет отрицательным. Поэтому через несколько миллионов вызовов стек будет переполнен и возникнет ошибка «stack overflow». В некоторых языках программирования предусмотрена «защита» от таких рекурсий. В них рекурсия из конца функции конвертируется в цикл, что не будет расходовать стековую память. Но подобная «оптимизация» вызовет другую, менее опасную проблему — «зацикливание».

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

В коде это выглядит так:

 int Object::getNumber(int index, bool& isChangeable)

{

  isChangeable = true;

  return getNumber(index);

}

int Object::getNumber(int index)

{

  bool noValue;

  return getNumber(index, noValue);

}

Глубокая рекурсия и ошибка «stack overflow»

Глубокая рекурсия — это такая рекурсия, которая имеет свое окончание через определенное время, поэтому она не бесконечная. Однако памяти стека не хватит для завершения такой рекурсии, поэтому ошибка «stack overflow» обеспечена. Обычно такая ситуация заранее просчитывается программистом,поэтому ее можно решить. Например, можно:

  • отыскать другой программный алгоритм для решения поставленной задачи, чтобы избежать применения рекурсии;

  • «вынести» рекурсию за пределы аппаратного стека в динамический;

  • и другое.

Глубокая рекурсия выглядит так:

void eliminateList(struct Item* that)

{

    if (that == NULL)

        return;

    eliminateList(that->next);

    free(that);

}

Проблемы с переменными в стеке и ошибка «stack overflow»

Если взглянуть на популярность возникновения «stack overflow error», то причина с проблемными переменными в стеке стоит на первом месте. Кроется она в том, что программист изначально выделяет слишком много памяти локальной переменной.

Например:

int function() {

     double b[1000000]

}

В данном случае может возникнуть такая ситуация, что массиву потребуется объем памяти, который стек не способен будет обеспечить, а значит, возникнет ошибка «stack overflow». 

Заключение

Ошибка «stack overflow» возникает довольно часто. Каждый конкретный случай ее возникновения требует собственного решения. Одна причина объединяет возникновение такой ошибки — невнимательность программиста. Если «stack overflow error» возникла, значит, программист где-то что-то упустил или не доглядел.

Источник

Форум мехмата ЮФУ

Загрузка…

Источник

  • Перепишите текст исправляя орфографические ошибки правильно
  • Переполнение стека встроенного языка на сервере 1с исправить ошибку
  • Перепишите текст исправив орфографические ошибки после оплаты начальной подписки вы получаете
  • Переплет сделался неотъемлемой деталью комнатного убранства ошибка
  • Перепишите текст исправив орфографические ошибки исполнитель получает вечный доступ