Как работает моя рекурсивная функция в C?
Я написал рекурсивную функцию на языке C, чтобы освободить память, выделенную программой, генерирующей дерево узлов. Однако я не могу понять, как это работает, но проверку проходит50. Возможно, я написал недостаточно хорошо, чтобы понять это.
Я пробовал следить за отладчиком, но просто не могу понять, как ему удается успешно проходить три поколения родителей.
Полагаю, мои основные вопросы:
Как эта функция освобождает снизу вверх дерево предков? Например. как и когда вызывается
free(p)? Это когда вызывается возврат? Я знаю, что важно не потерять какие-либо узлы, но я не знаю, как этого здесь избежать.Следуя отладчику и проходя по коду,
free(p)явно не вызывается до тех пор, пока не покажется, что достигнут родительский узел - например.free_family(p->parents[0])был вызван дважды, а затем последующий вызовp->parents[0]имеет значение NULL, прежде чемfree(p)освободит этот стек от вызова. Я вообще не могу понять, как это работает.
Извиняюсь за нубский вопрос — в настоящее время я новичок в программировании и слежу за CS50x.
Я не буду публиковать весь код, если это не требуется, но каждый узел определяется следующим кодом. Существует 3 поколения этих узлов. Последнее поколение родителей получает родительские указатели NULL.
typedef struct person
{
struct person *parents[2];
char alleles[2];
} person;
Моя рекурсивная бесплатная функция:
// Free `p` and all ancestors of `p`.
void free_family(person *p)
{
// TODO: Handle base case
if (p == NULL)
{
return;
}
// TODO: Free parents recursively
free_family(p->parents[0]);
free_family(p->parents[1]);
// TODO: Free child
free(p);
}
Затем, прежде чем каждый вызов вернется, этот уровень освобождается.
Извините за путаницу. Чтобы уточнить: я понимаю, что это дочерние узлы, но в задаче они представляют биологических родителей, и поэтому код распространения CS50 заранее определил структуры с указателями родительского массива. Немного сбивает с толку то, что они указывают на дочерние узлы, которые представляют родителей (а впоследствии и бабушек и дедушек). Спасибо вам за помощь.
Это представление является семантическим только в контексте всего дерева. В контексте стека вызовов при любом вызове вашей функции parents всегда относится к прямым родителям текущего узла, на который указывает p. Когда вы делаете рекурсивный вызов, вы просто передаете одно поддерево текущего узла. И прежде чем продолжить, все это поддерево (и его поддеревья и т. д.) удаляется. По возвращении из обоих рекурсивных вызовов вы теперь знаете, что ваш узел удалил свои поддеревья, и поэтому вы можете удалить узел.
Предложите ввести [c] "recursion" "how" is:answer в строку поиска выше. Доступно МНОГО примеров. Рекурсия может быть сложной концепцией на старте. Потратив время на изучение множества различных примеров, вы сможете найти неуловимую точку опоры, которая подойдет именно вам, и вы сможете начать осваивать эту концепцию структуры данных. Стоит!! Удачи...
Кстати: Чарльз Дарвин — известный человек, женившийся на своей двоюродной сестре. Вместе у этой пары было обычно четверо родителей. Однако на одно поколение дальше «вверх» можно найти только 6, а не 8 «бабушек и дедушек» этой пары. Я упоминаю об этом только для того, чтобы познакомить вас с тем, что «данные из реальной жизни» НАМНОГО сложнее, чем четкие, четко определенные и наивные модели данных. Всегда будьте готовы к непредвиденным сложностям, возникающим при кодировании. Некоторые говорят: «10% работы решают 90% проблемы, а затем 90% работы решают последние 10%, которые не были учтены в начале проекта». Ваше здоровье!
@Fe2O3 — спасибо за советы, это отличный анекдот, который стоит выучить. Спасибо, что поделился!
Ответы 1
person1
|- person2
| |- person4
| |- person5
|- person3
| |- person6
| |- person7
Предположим, это ваше дерево. Все наоборот: человек 1 самый младший, у него есть родители человек 2 и человек 3.
Когда вы переходите к free person1, ваш код выполняет следующее:
- Want to free person1, but the parents are to be freed first
- Try to free person2
- Try to free person4
- person4 has no first parent, so no more recursion. Free person4
- Try to free person5
- person5 has no second parent, so no more recursion. Free person5
- Now that yo're done freeing the parents of person2, you actually free person2
- Repeat above for person3
- Now that you are done freeing the parents for person1, actually free person1
На самом деле это довольно просто. Чтобы понять это, вам нужно следовать потоку управления. Уделите некоторое время самому коду и попытайтесь проследить поток управления построчно. Это не асинхронный или многопоточный код, и он имеет очень линейную последовательность выполнения. Постарайтесь не потеряться в отладчике. Только после того, как вы хорошо разберетесь в том, как обычно работает поток управления, вы сможете эффективно использовать отладчик.
Обновлено: Дополнительные примечания
Здесь есть отдельные вопросы:
- Как программа избегает потери каких-либо узлов?
- Почему вызывается функция free() при ее вызове?
- Когда на самом деле вызывается free()?
Что касается 1.:
Как обсуждалось в другом ответе, программа избегает потери каких-либо узлов, освобождая дочерний элемент только после освобождения родителей. Здесь нет никакой магии C, и ничего не происходит за кулисами. Как программист, вы разместили эти команды для выполнения в таком порядке, чтобы создать такой эффект. Вы бы сделали это, зная, что как только вы освободите ребенка, вы потеряете ссылки на родителей ребенка (и, как следствие, на всех предков), и их никогда нельзя будет освободить. Поэтому обязательно освободите все из них, прежде чем избавиться от ссылок на них.
Это подводит нас к 2. :
free вызывается в вашем коде после освобождения родителей.
Однако вы можете так же легко сначала вызвать free() без каких-либо других изменений. Затем, когда вы пойдете освобождать родителей, вы обнаружите нули. В лучшем случае у вас появятся сироты. В худшем случае вы совершите ошибку. Сам C не помешает вам сделать это. Могут существовать IDE и инструменты статического анализа кода, которые предупредят вас. Компилятор может даже предупредить вас. Но что касается кода C, то он технически допустим.
Вы можете избежать этой проблемы, сохранив последовательность «сначала освободите ребенка», сначала скопировав ссылки на родителей в другие переменные, затем освободив дочерний элемент, а затем освободив родителей. Существуют (редкие) случаи использования такого подхода.
Все зависит только от вас, решать, как это сделать, сделать все правильно или выстрелить себе в ногу.
Это подводит нас, наконец, к 3:
free вызывается, когда вы, программист, вызываете его. Вы решаете, когда это делать, исходя из порядка написания программы и различных структур управления, таких как ifs и fors, а также вызовов функций, которые у вас есть.
Рекурсивные функции — это просто функции. В других, более сложных языках программирования рекурсивные функции — это обычные функции в забавных шляпах. В C они даже этого не делают. Вам не нужно сообщать компилятору, что он рекурсивный. Никто не действует за кулисами, чтобы убедиться, что вы не выстрелите себе в ногу. Когда вы вызываете функцию, пока C может найти ссылку для вызова с этим именем (символом), она это сделает.
В free() тоже нет ничего особенного. Это тоже просто вызов функции. С таким же успехом это может быть do_something_else() вместо free(). Если не считать того факта, что память не будет освобождена (поскольку в этом гипотетическом коде нет вызова free()), она будет вести себя точно так же.
Спасибо за объяснение, это действительно полезно. Значит, free(p) выполняется только тогда, когда функция возвращается?
free(p) выполняется только при достижении этой строки. Эта строка достигается только после вызовов освобождения родителей из-за того, как написан ваш код, который сначала должен выполниться полностью и вернуться, только после чего поток управления перейдет к следующим строкам. Вы можете вызвать free() перед вызовами free для родителей, чтобы получить другое поведение, но тогда ваш код должен будет быть более сложным.
Я предлагаю вам потратить некоторое время на изучение базового потока управления в C. Большинство языков программирования работают именно так. Операторы выполняются один за другим, в том порядке, в котором они написаны, с очень специфическими способами управления потоком, такими как циклы, условные выражения и вызовы функций. Вам нужно хорошо ознакомиться с этой идеей задолго до того, как вы сможете эффективно использовать отладчик.
Это имеет большой смысл. Спасибо за объяснение, я новичок в рекурсии, поэтому эту концепцию я все еще не понимаю. Что касается понимания потока управления, есть ли какие-либо инструменты, которые могут помочь? Я ценю, что отладчик, который пошагово выполняет код, может это сделать, но вы упомянули, что сосредоточились на потоке управления - вы имеете в виду умственное упражнение? Редактировать: только что увидел ваш недавний комментарий - я знаком с потоком управления, но когда дело доходит до рекурсии, я думаю, что это добавляет необходимый дополнительный уровень понимания.
Следует признать, что большинство из нас, вероятно, узнали об этом в классе или из учебника. Это очень фундаментальное понятие программирования, и я не могу сказать вам, где и когда я впервые о нем узнал. Это просто то, что есть. Умственное упражнение, вероятно, будет хорошим началом. Вы можете поиграть с кодом с помощью операторов печати и посмотреть, как управление проходит через программу. Для простого C, не делая более сложных вещей, вы можете предположить, что в любой момент времени выполняется только один оператор. Базовый курс программирования также может решить эту проблему, если таковые существуют.
Рекурсия ничем не отличается от обычных функций. Просто относитесь к рекурсивному вызову как к обычному вызову функции. Что отличает рекурсию, так это то, что вам нужно подумать о таких вещах, как повторный вход (безопасно ли одновременное выполнение нескольких копий функции) и какую глубину рекурсии вы можете выдержать с точки зрения использования памяти. Ничто из этого не касается вашего кода и вообще не влияет на поток управления.
Может помочь, если вы запишите вместе с входными данными вашего примера последовательность «команд», которые будут выполняться. Разверните и сгладьте все ветвления, превратив программу в одну длинную последовательность, и посмотрите, что получится. Это будет утомительное занятие, но оно поможет вам увидеть, что происходит. Список, который я включил в свой ответ, представляет собой ленивую попытку сделать это, вы можете рассмотреть его более подробно.
Большое спасибо за ваш совет. Я бы сказал, что в вашем ответе нет ничего ленивого, и вы очень помогли. Я боялся публиковать такой простой вопрос, но теперь у меня есть хорошее направление для моего обучения. Спасибо.
Я добавил в ответ некоторые дополнительные мысли, которые могут оказаться вам полезными.
Он освобождает снизу вверх, потому что он не освобождает текущий узел до тех пор, пока он не рекурсивно перейдет в два дочерних узла (которые вы сбивчиво называете
parents). Рекурсивный вызов делает то же самое — он освобождает потомков, прежде чем освободить себя. В конце концов он достигает листьев и перестает повторяться.