Блог

Главная - Вопросы по программированию - Есть ли смысл, если вместо простого вызова функции в псевдокоде записывается функция возврата (особенно в отношении CLR)?

Есть ли смысл, если вместо простого вызова функции в псевдокоде записывается функция возврата (особенно в отношении CLR)?

#algorithm #tree #pseudocode

#алгоритм #дерево #псевдокод

Вопрос:

Есть ли смысл, если вместо простого вызова функции в псевдокоде записывается функция возврата (особенно в отношении CLR)?

например, является

 if x == NIL or x.key == k
   return x
if x.key <= k
   return Tree-Search(x.left,k)
else 
   return Tree-Search(x.right,k)

равно

 if x == NIL or x.key == k
   return x
if x.key <= k
   Tree-Search(x.left,k)
Tree-Search(x.right,k)

Комментарии:

1. Вы знаете, что делает «return»?

2. Псевдокод не стандартизирован, поэтому он может использовать любое согласованное соглашение. Тем не менее, здравый смысл подсказывает, что второй фрагмент не эквивалентен, даже если мы примем соглашение, в котором последний оператор неявно возвращается, поскольку у него есть путь, где Tree-Search вызывается дважды.

3. Если ваш пример является псевдокодом, почему вы пометили его C?

4. Извините, я все еще не вижу своей ошибки, возвращаемое значение останавливает вызов, но разве оно не вызывает функцию?

Ответ №1:

Это return , безусловно, необходимо. Предположительно, код в кавычках является телом Tree-search функции, поэтому на самом деле он будет выглядеть примерно так:

 function Tree-Search(x, k)
    if x == NIL or x.key == k
       return x
    if x.key <= k
       return Tree-Search(x.left, k)
    else 
       return Tree-Search(x.right, k)

Теперь предполагается, что эта функция возвращает узел из дерева — узел, ключ которого равен k . Если вы не используете return , то функция ничего не вернет (за исключением случая, когда первое if условие истинно).

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

Оба кода без return и с return выполняют рекурсивный вызов. Разница в том, что версия без return ничего не делает с тем, что она получает от этого вызова: она полностью игнорирует его. Тот, у return которого будет фиксироваться возвращаемое значение и возвращать то же значение своему собственному вызывающему.

Представьте, что выполнение выполнило несколько вложенных рекурсивных вызовов, тогда вы можете представить это состояние как дерево рекурсии, где каждый из этих рекурсивных вызовов находится в ожидании; ожидая возврата более глубокого вызова. Давайте предположим, что последний имеет x.key == k . В этом случае x возвращается именно это. Но он возвращается не первоначальному вызывающему, а рекурсивному вызывающему, который ожидал результата. Если возвращаемое значение не возвращается снова вызывающему, который находится на одном уровне выше в дереве рекурсии, то этот вызывающий не узнает об этом совпадении x . Таким образом, каждый вызывающий должен вернуть это x и вернуть его также вверх по дереву рекурсии. Наконец, первоначальный вызывающий тоже получит x .