Хвостовая рекурсия, как исключить оператор return? - PullRequest
Новая
       7

Хвостовая рекурсия, как исключить оператор return?

0 голосов
/ 05 января 2019

Вот хвостовая рекурсивная C # -программа, которая суммирует квадраты от 1 до 10. Она работает, за исключением последней еще в AddSquares2(). Это не работает, потому что C #, кажется, требует оператора возврата в каждом пути в методе, который возвращает значение. Однако мне не нужно использовать оператор return в хвостовом рекурсивном методе, таком как этот. Смотрите комментарий.

Это просто особенность C #? Или есть способ сообщить компилятору, что я знаю, что делаю, и не хочу, чтобы каждый путь возвращал значение?

Вот моя программа: 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Recursive
{
    class Program
    {
        static void Main(string[] args)
        {
            int start = 1;
            int end = 10;
            int sum = 0;
            AddSquares(start, end, sum);
            sum = AddSquares2(start, end, sum);
        }

        private static int AddSquares2(int start, int end, int sum)
        {
            Console.WriteLine($"AddSquares2({start}, {end}, {sum})");
            if (start > end)
                return (sum);
            else
                //should not have to return anything here
                return(AddSquares2(start + 1, end, sum + start * start));
        }

        private static void AddSquares(int start, int end, int sum)
        {
            Console.WriteLine($"AddSquares({start}, {end}, {sum})");
            if (start > end)
                Console.WriteLine($"  The total sum is {sum}");
            else
                AddSquares(start + 1, end, sum + start * start);
        }
    }
}

Вот вывод: 

 AddSquares(1, 10, 0)
    AddSquares(2, 10, 1)
    AddSquares(3, 10, 5)
    AddSquares(4, 10, 14)
    AddSquares(5, 10, 30)
    AddSquares(6, 10, 55)
    AddSquares(7, 10, 91)
    AddSquares(8, 10, 140)
    AddSquares(9, 10, 204)
    AddSquares(10, 10, 285)
    AddSquares(11, 10, 385)
      The total sum is 385
    AddSquares2(1, 10, 0)
    AddSquares2(2, 10, 1)
    AddSquares2(3, 10, 5)
    AddSquares2(4, 10, 14)
    AddSquares2(5, 10, 30)
    AddSquares2(6, 10, 55)
    AddSquares2(7, 10, 91)
    AddSquares2(8, 10, 140)
    AddSquares2(9, 10, 204)
    AddSquares2(10, 10, 285)
    AddSquares2(11, 10, 385)
      The total sum is 385

Ответы [ 3 ]

0 голосов
/ 05 января 2019

Единственный способ, которым вы можете «избежать неприятностей», не используя возврат, - вместо этого выдать ошибку. Это не имеет смысла делать это в вашей ситуации.

Вы также можете избежать использования возврата, не указав путь к коду (в этом случае не используйте предложение else)

Однако вы правильно сделали, что вернули результат рекурсивного вызова AddSquares2 в своем другом. Если вы этого не сделаете, ваш код для AddSquares2 никогда не будет повторяться и не будет работать (так что вы ДЕЙСТВИТЕЛЬНО должны что-то вернуть! Ааа).

Рекурсивные методы должны иметь точку внутри себя, куда они возвращаются, не вызывая себя (чтобы не допустить бесконечного повторения рекурсии), а также точку, где они вызывают себя (чтобы поддерживать рекурсию на некоторое время)

Вероятно, академическое упражнение, но, возможно, стоит упомянуть, что рекурсия - это форма цикла, которая (ab) использует стек вызовов для обеспечения конструкции цикла. Рекурсивные методы могут (и должны, imho) выполняться с использованием обычных циклов

0 голосов
/ 05 января 2019

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

Однако C # не так близок к металлу, как этот. Когда мы пишем C #, мы указываем intent и позволяем компилятору (и / или JITter) позаботиться об оптимизации, такой как хвостовые вызовы, встраивание методов и тому подобное. Наличие ключевого слова C # return не обязательно подразумевает или требует некоторой очистки стека. Вместо этого он указывает намерение программиста .

Если мы позволим вам пропустить «возврат», это значительно усложнит работу компилятора по пониманию ваших намерений. Знал ли программист о возможной оптимизации и намеревался концептуально «вернуть» метод, или он имел в виду явно ничего не делать с результатом. C # предполагает последнее.

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

0 голосов
/ 05 января 2019

Короче говоря, метод в C # должен иметь return на всех путях выполнения кода, вам это может не понравиться, но это так. То же самое в математике все функции имеют результат, это то, что функции делают.

Теперь, сказав, что результат может быть неопределенным, Infinity, 0, null, или в случае C # с типом возврата, не допускающим обнуления int, он может быть 0. Что имеет смысл, учитывая сигнатуру .

Как насчет того, чтобы притвориться на секунду, что мы могли бы просто прекратить выполнение кода в точке вашего остального. Если вызывающий метод полагается на результат (и они обычно это делают), и даже если метод завершился так, как вы предлагаете, то что будет думать вызывающий объект? ну, это должно быть в состоянии справиться с отсутствием значения, или нет.

Если вам действительно нужно знать, что ваш else не генерирует значение, сделайте свою подпись int? (обнуляемая) и верните null, чтобы вызывающий знал, что делать. если это просто отсутствие числа для суммы, тогда сделайте его равным 0, никакого вреда не будет

...