Как заставить мою функцию быть рекурсивной? (Java)

Question

Мне нужно сделать рекурсивную функцию, которая получит стек int и выведет сумму квадратов элементов в стеке. Вот что у меня есть

public int sum_sqr_rec(Stack<Integer> stk){
int sum = 0;
for (int i=0; i<stk.size(); i++){
sum += (stk.get(i) * stk.get(i));
}
return sum;
}

Answer 1

Самое важное, что вам нужно определить для рекурсивной функции, - это когда ее завершать.

Вторым важным моментом, который следует учитывать, является то, что возвращать, когда вы завершаете его. Когда вы начинаете добавлять числа, вы начинаете с sum = 0. Из рекурсивной функции, которая должна вычислять сумму чисел, одно и то же значение (т. Е. 0) может быть возвращено при его завершении. Аналогично, из рекурсивной функции, которая должна возвращать произведение чисел, вы можете вернуть 1 при завершении.

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.add(2);
        stack.add(3);
        stack.add(4);
        stack.add(5);
        System.out.println(sum_sqr_rec(stack));
    }

    static int sum_sqr_rec(Stack<Integer> stk) {
        if (stk.isEmpty()) {
            return 0;
        }
        int n = stk.pop();
        return n * n + sum_sqr_rec(stk);
    }
}

Вывод:

54

Answer 2

Обратите внимание, что я использую интерфейс Deque, а не класс Stack напрямую (в документации сказано, что его следует использовать вместо класса Stack).

    public int recursive(Deque<Integer> stk){
        if (stk.Empty()){
            return 0;
        }
        return Math.pow(stack.pop(), 2) + recursive(stk);
    }

Answer 3

Вы можете использовать рекурсию следующим образом:

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.add(2);
        stack.add(2);
        stack.add(4);
        stack.add(5);
        System.out.println(sum_sqr_rec(stack));
    }

    public static int sum_sqr_rec(Stack<Integer> stack) {
        if (stack.isEmpty())
            return 0;
        return stack.peek() * stack.pop() + sum_sqr_rec(stack);
    }

Answer 4

Множество способов сделать это. Но если вы не хотите уничтожать стек, вы можете сделать это следующим образом. Стек восстанавливается во время процесса возврата.

• n выталкивается. Это истощает стек чисел и сохраняет n в локальном стеке вызовов для последующего использования.

• Квадрат элемента сохраняется в стеке вызовов метода в k

• r инициализируется для окончательного подсчета.

• Когда стек пуст, просто вставьте pu sh n обратно на stk и верните суммы сохраненных квадратов.

static int sum_sqr_rec(Stack<Integer> stk) {
      int n = stk.pop();
      int k = n*n;
      int r = 0;
      if (!stk.isEmpty()) {
            r = sum_sqr_rec(stk);
      }
      stk.push(n);
      return r + k;
}

Использование этой последовательности вызовов операторов.

System.out.println(stack);
System.out.println(sum_sqr_rec(stack));
System.out.println(stack);

В результате получается следующее

[2, 3, 4, 5]
54
[2, 3, 4, 5]