Описание тега tail-recursion
Хвостовая рекурсия - это рекурсивная стратегия, при которой функция выполняет некоторую работу, а затем вызывает себя. "Хвост" относится к тому факту, что рекурсия находится в самом конце функции. Многие - особенно функциональные - компиляторы языков программирования могут превращать эти типы вызовов в итерацию, что означает, что хвостовая рекурсия в поддерживаемых языках может использоваться, не опасаясь переполнения стека, независимо от количества вызовов.
4
ответа
Оптимизирована ли следующая функция хвостового вызова?
Я новичок в haskell (впервые пробую программировать) и просто пробую различные упражнения из книги "Реальный мир haskell". Может кто-нибудь поправить меня и сказать, оптимизирована ли нижеуказанная функция или нет? Если да, то не могли бы вы поправи…
19 авг '14 в 14:40
1
ответ
F# хвост рекурсивный вызов
У меня есть этот код: let rec collect ( t : BCFile list ) ( acc : Set<BCFile> ) : Set<BCFile> = match t with | [] -> acc | hr::tl -> collect ( tl ) ( Set.union acc ( FindSourceFilesForTarget ( hr ) ) ) let s = collect (Set.toList t…
27 авг '13 в 19:54
1
ответ
Хвостовая рекурсия и CPS
Я застрял на этой проблеме некоторое время. Я передаю предикат и список другой функции в схеме. Если предикат дает вам истину, вы добавляете его в свой список ответов, иначе пропускаете. Например, (myfilt positive? '(1 -2 3)) должно быть (1 3), Но я…
11 фев '14 в 03:24
1
ответ
Выход из хвостового файла - В Perl
У меня есть этот кусок кода, который в основном хвост файла. Этот файл заполняется почти 100 записями каждую секунду. open (MYFILE, 'output.txt'); for (;;) { while (<MYFILE>) { chomp; my $test=$_; if ($test =~ m/^ok/) { $passed++; print "Numbe…
18 окт '11 в 20:44
2
ответа
Компиляторы семейства ML делают какую-либо сложную оптимизацию для хвостовых вызовов?
Я (полагаю) следующее определение функции является хвостово-рекурсивным: fun is_sorted [] = true | is_sorted [x] = true | is_sorted (x::(y::xs)) = if x > y then false else is_sorted (y::xs) Тривиально, это эквивалентно следующему объявлению fun i…
17 июл '14 в 13:38
1
ответ
Рекусивное сканирование через иерархию списка различных типов записей
У меня есть структура данных, которая состоит из списка записей F#, для которого один из членов сам является списком записей другого типа, так что примерно до 4 уровней глубокой иерархии. Код, который я должен создать для этой структуры, немного мно…
08 авг '12 в 08:51
2
ответа
Странная оптимизация рекурсии с помощью Java
Я столкнулся с некоторыми странными результатами, когда пытался ответить на этот вопрос: как улучшить производительность рекурсивного метода? Но вам не нужно читать этот пост. Я дам соответствующий контекст здесь. Это может показаться длинным, но на…
04 июн '12 в 20:00
1
ответ
Деконструкция рекурсивного процесса - SICP
Рассмотрим следующее определение: (define foo (lambda (x y) (if (= x y) 0 (+ x (foo (+ x 1) y))))) Что такое тестовое выражение? (напишите фактическое выражение, а не его значение) Я думаю, что это просто (если (= x y), но он-лайн репетитор MIT 6.00…
08 июн '13 в 01:40
3
ответа
Сокращение использования стека в рекурсивной функции в C++
У меня есть программа, которая рассчитывает факториал любого числа. Когда я пытаюсь сделать это с большим числом, таким как 100 000, оно останавливается, прежде чем оно достигнет 0. Я предполагаю, что это какой-то механизм безопасности для предотвра…
24 ноя '16 в 19:04
0
ответов
Конец хвоста против факториала форварда в питоне
У меня есть какая-то ручка с рекурсией. Рекурсивная функция - это функция, которая вызывает себя для запуска, что-то вроде цикла. Однако у меня проблема с хвостовой и прямой рекурсией. Из того, что я понимаю, хвостовой конец выполняет вычисления на …
01 окт '15 в 04:24
2
ответа
Я думал, что это уже хвост рекурсивный. Но если нет, то как мне сделать это так?
Не лучшее название вопроса, я согласен. Но я не мог придумать что-то еще. Сожалею. При написании простого кода односвязного списка в Groovy я хочу добавить метод, который принимает два списка и добавляет правый к левому. Это то, что я придумываю. pr…
14 мар '15 в 19:09
3
ответа
Почему скаляры не могут оптимизировать хвостовую рекурсию в определенных сценариях?
Почему scalac (компилятор Scala) не оптимизирует хвостовую рекурсию? Вызовы кода и компилятора, демонстрирующие это: > кошка foo.scala класс Foo { def ifak (n: Int, acc: Int): Int = { если (n == 1) в соответствии еще ифак (n-1, n*acc) } } > скалак f…
09 ноя '09 в 06:24
1
ответ
Как я могу сделать эту функцию хвостовой рекурсивной?
Мне интересно, если мой алгоритм хвостовой рекурсии; Я только что сделал эту функцию для красивой печати массива в PHP: function get_pretty_output($value, $first=true, $indent = ''){ if (!is_array($value)) { return $value.PHP_EOL; } if (empty($value…
18 дек '13 в 20:34
2
ответа
Хвост-рекурсия и скалярные обещания
В настоящее время я играю с неблокирующими фьючерсами Scalaz aka. Обещания. Я пытаюсь сделать следующую функцию хвостовой рекурсивной: @tailrec private def repeat( res: Promise[I] ):Promise[I] = res map p flatMap { (b:Boolean) => if( b ) repeat( …
09 май '11 в 12:59
1
ответ
Схема для начинающих: процедуры, которые возвращаются сами
Это пример из книги, которую я читаю: 1 (define (length items) 2 (define (length-iter a count) 3 (if (null? a) 4 count 5 (length-iter (cdr a)(+ 1 count)))) 6 (length-iter items 0)) То, что я не понимаю, как можно length-iter знать о графе? Первый ра…
16 сен '12 в 19:37
1
ответ
Хвост-рекурсия в FParsec
Я столкнулся с проблемой парсеров, имеющих две ветви рекурсии. Чтобы легче продемонстрировать проблему, я использую простую грамматику лямбда-исчисления из статьи, написанной Лукой Болоньезе, в качестве примера: <expression> ::= <name> |…
12 фев '12 в 19:32
1
ответ
(Как) я могу сделать эту монадную привязку хвостовой рекурсивной?
У меня есть эта монада под названием Desync - [<AutoOpen>] module DesyncModule = /// The Desync monad. Allows the user to define in a sequential style an operation that spans /// across a bounded number of events. Span is bounded because I've …
03 янв '15 в 13:35
2
ответа
Хвостовая рекурсия с Groovy
Я кодировал 3 факторных алгоритма: Во-первых, я ожидаю провала из-за переполнения стека. Нет проблем. Во-вторых, я пытаюсь вызвать рекурсивный вызов, преобразовать предыдущий алгоритм из рекурсивного в итерационный. Это не работает, но я не понимаю …
10 сен '11 в 21:42
5
ответов
Какие компиляторы C++, если таковые имеются, выполняют оптимизацию хвостовой рекурсии?
Мне кажется, что было бы очень хорошо выполнить оптимизацию хвостовой рекурсии как в C, так и в C++, но при отладке я никогда не вижу стека фреймов, который указывает на эту оптимизацию. Это хорошо, потому что стек говорит мне, насколько глубока рек…
29 авг '08 в 07:35
2
ответа
Эта функция использует хвостовую рекурсию?
Мне интересно, оптимизирует ли oCaml этот код для хвостовой рекурсии, и если да, то F#? let rec sum xs = match xs with | [] -> 0 | x :: xs' -> x + sum xs'
27 фев '10 в 11:54