Как вам лучше всего преобразовать рекурсивную функцию в итеративную?

Question

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

public static void foo(int number) { 
    if (number > 0) { 
     foo(number/2); 
     System.out.print(number % 2); 
    } 
} 

Мне нужно преобразовать эту функцию, чтобы быть нерекурсивна, но я борюсь с ним, потому что System.out.print(number % 2) происходит после рекурсивного вызова.

Answer 1

Вы всегда можете имитировать стек, конечно, но во многих случаях вы можете преобразовать его в полностью бесуровневое решение. (Я не уверен на 100%, но думаю, что преобразование без стека возможно только для primitive recursive functions.Я не вижу никакого способа, как Ackermann function может быть вычислен без какого-либо стека.)

В любом случае, для большинства случаев на практике (и во всех случаях в классной комнате) можно найти способ. Здесь мы можем использовать счетчик трюк:

public static void foo(int number) { 
    for (int divisor = 1; divisor <= number; divisor *= 2) { 
     System.out.print((number/divisor) % 2); 
    } 
} 

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

Answer 2

Вы можете использовать Deque, чтобы следить за то, что вам нужно распечатать

public static void foo(int number) { 
    Deque<Integer> stack = new ArrayDeque<Integer>(); 
    while (number > 0) { 
     stack.push(number); 
     number = number/2; 
    } 
    //iterate over the stack... 
    while(!stack.isEmpty()){ 
     Integer myInt = stack.pop(); 
     //your code here 
    } 
} 

Answer 3

Пожалуй prepending в строку?

public static void foo(int number) { 
    String r = ""; 
    while(number > 0) { 
     r = (number%2)+r; 
     number = number/2; 
    } 
    System.out.print(r); 
} 

Answer 4

лучший способ имитировать рекурсию ИТС с использованием стека, и используя толчок и поп, так что, как работает рекурсия:

public static void foo2(int number) 
{ 
    Stack st = new Stack(); 
    for(int i=number;i>0;i=i/2) 
    { 
     st.push(i%2); 
    } 
    while(!st.empty()) 
    { 
     System.out.print(st.pop()); 
    } 
} 

Answer 5

Общий подход к recursion-elimination является повторить, как компилятор performs recursion с использованием Stack. Этот подход может быть применен для преобразования любой рекурсивной программы в нерекурсивную.

Способ использования Stack предназначен для хранения различных stack frames, соответствующих каждому рекурсивному вызову. Каждый кадр стека должен каким-то образом отслеживать свою позицию во время выполнения кода. Чем лучше мы различаем эти стековые кадры (т. Е. Основные шаги выполнения), тем проще наше решение.

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

---

A) проверить, если number is > 0 и вызвать foo прохождения number/2 в качестве аргумента

B)number % 2

---

Или в коде:

// all marked A are a single "step" 
public static void foo(int number) { 
    if (number > 0) {     // A 
     foo(number/2);    // A 
     System.out.print(number % 2); // B 
    } 
} 

Так давайте создадим StackFrame класс, который будет тиражировать это:

static class StackFrame { 
    int number; 
    char nep; // Next Execution Position ('A' or 'B') 
    StackFrame(int number, char nep) { 
     this.number = number; 
     this.nep = nep; 
    } 
} 

Переменная nep используется для хранения следующей позиции при выполнении программы для каждого StackFrame.

Программа будет относиться к части исполнения A и B:

A) Программа использует Stack из StackFrames и толкает новую StackFrame каждый раз, когда он тиражирование рекурсивный вызов и в то время как условие number > 0 верно. (Это будет базовый случай в вашей рекурсии)

B) После этого условия (базовый случай) достигается, мы можем начать появляться StackFrames стека так же, как компилятор делает и печатать нашу нужное значение (number % 2).

Вот как этот подход будет выглядеть:

public static void iterative(int number) { 
    Stack<StackFrame> stack = new Stack<StackFrame>(); 
    stack.push(new StackFrame(number, 'A')); 
    while(!stack.isEmpty()) { // run until we have stack frames 
     StackFrame top = stack.peek(); 
     switch(top.nep) { // determine next execution step 
     case 'A': 
      top.nep = 'B'; // set next execution step 
      if(top.number/2 > 0) { // check base case and push current stack frame if base case is true 
       stack.push(new StackFrame(top.number/2, 'A')); 
      } 
      break; 
     case 'B': 
      System.out.print(top.number % 2); 
      stack.pop(); // end current stack frame 
      break; 
     } 
    } 
} 

Here is a full sample program

Пример вывода программы для number = 211:

Recursive output: 11010011 
Iterative output: 11010011 

Вот некоторые great visual examples для устранения рекурсии

Answer 6

Просто для другой перспективы по этому вопросу, поскольку у вас уже есть много ответов.

Это правда, что весь подход к решению рекурсии - это использование стека. Однако, если вы точно знаете, что именно решите, вы можете найти альтернативное решение. Или, может быть, не альтернатива точно - только одна, которая будет более компактной.

В этом случае функция дает двоичное представление параметра для целых чисел больше нуля.

Вы можете захотеть использовать:

public static void foo(int number) { 

     if (number > 0) { 
      System.out.print(Integer.toBinaryString(number)); 
     } 

    } 

Но это, конечно, может только заработать очки за дерзость в тесте.

Так вот адаптация пути Java на самом деле делает это:

public static void foo(int number) { 

    if (number > 0) { 
     char[] chars = new char[32]; 
     int charPos = 32; 
     char[] digits = { '0', '1' }; 

     do { 
      chars[--charPos] = digits[number % 2]; 
      number /= 2; 
     } while (number > 0); 

     System.out.print(new String(chars, charPos, 32 - charPos)); 
    } 
} 

Это, по сути, с использованием стека, но не очень сложный. Стек - это просто массив символов, которые вы начинаете заполнять с конца, и отправляйтесь в начало. Вы можете использовать такой массив вместо коллекции, потому что известно, что int содержит не более 32 бит. Таким образом, вы никогда не столкнетесь с границами массива. По правде говоря, потому что вы работаете только с положительными числами, это может быть даже 31-символьный массив.

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

Фактические операторы, используемые Java немного отличаются:

 do { 
      chars[charPos--] = digits[number & 1]; 
      number >>>= 1; 
     } while (number != 0); 

потому, что смещение и маскирование являются более эффективными, чем операции дивизия. Если вы используете эту версию, она так же эффективна, как и с использованием Integer.toBinaryString().