Задача с рекурсией

@Nahmir · Регистрация: 06.04.2021

Студворк — интернет-сервис помощи студентам

Добрый вечер, нужна помощь в решении задачи.
Задача решена на 70%, но дальше не получается, залип на 40 минут и уже ничего не понимаю. Хотя решение, кажется, лежит на поверхности.

Так вот, суть задачи.

Условие:
Написать рекурсивный метод writeSequence, который принимает целочисленный параметр n и печатает симметричную последовательность из n чисел, состоящую из убывающей последовательности чисел, заканчивающихся 1, которая продолжается возрастающей последовательностью чисел, начинающихся с 1. См. примеры.

Особенность:
Обратите внимание, что для нечетных n последовательность содержит только одну 1, а для четных – две 1.

Примеры:

input: 9
output: 5 4 3 2 1 2 3 4 5

input: 8
output: 4 3 2 1 1 2 3 4

Моя проблема:
Не понимаю как реализовать "реверс" второй половины чисел, то есть у меня получается так:

input: 8
output: 4 3 2 1 1 4 3 2

Код программы:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package javaapplication53;
 
import java.util.Scanner;
 
public class JavaApplication53 {
    
    private static void counter(int n) {
        if (n <= 1) {
            return;
        }
        int x = n / 2;
        if (n % 2 == 0) {
            left(x);
            System.out.print("1 1");
      } 
        if (n%2 == 1){
            x++;
            left(x);
            System.out.print("1");
        }
        right(x);
    }
 
    private static void left(int l) {
        if (l < 2) {
            return;
        }
        System.out.printf("%d ", l);
        left(l - 1);
    }
    
    private static void right(int r) {
        int i = 2;
        if (i > r) {
            return;
        }
        System.out.printf(" %d", r);
        right(r - 1);
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("WriteSequence");
        int n = in.nextInt();
        counter(n);
    }
}

@Coffeini · 19.04.2021, 23:07

А зачем здесь рекурсия...?

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 public static void main(String[] args) {
        int n = 15;
        StringBuilder result = new StringBuilder();
        for (int i = n / 2 + n % 2; i > 1; --i) {
            result.append(i).append(" ");
        }
        if (n % 2 == 0) {
            result.append("1");
            StringBuilder rev = new StringBuilder(result).reverse();
            result.append(" ").append(rev);
        } else {
            StringBuilder rev = new StringBuilder(result).reverse();
            result.append("1").append(rev);
        }
        System.out.println(result);
    }

@Nahmir · 19.04.2021, 23:09 **[ТС]**

Мы сейчас проходим тему рекурсии, поэтому эта задача должна делаться именно через рекурсию

@xoraxax · 19.04.2021, 23:12

Сразу вперёд и назад добавляй число.
1, 212, 32123...

@Coffeini · 19.04.2021, 23:16

Ну вот....

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {
    public static StringBuilder rec(int i, StringBuilder result) {
        if (i <= 1) {
            return result;
        }
        return rec(i - 1, result.append(i).append(" "));
    }
 
    public static void main(String[] args) {
        int n = 17;
        StringBuilder result = rec(n / 2 + n % 2,new StringBuilder());
 
        if (n % 2 == 0) {
            result.append("1");
            StringBuilder rev = new StringBuilder(result).reverse();
            result.append(" ").append(rev);
        } else {
            StringBuilder rev = new StringBuilder(result).reverse();
            result.append("1").append(rev);
        }
        System.out.println(result);
    }
}

@Tavashi · 19.04.2021, 23:53

Nahmir, рекурсия, по достижении базового случая, возвращает (продолжает) работу программы с места ее вызова. То есть, вы можете после вызова рекурсивного метода добавить вывод значения n (l или r в вашем случае), которое метод будет помнить на момент вызова:

Java
1
2
3
4
5
6
7
8
9
10
11
...
    private static void left(int l) {
        if (l < 2) {
            return;
        }
        System.out.printf("%d ", l);
        left(l - 1);
        System.out.printf("%d ", l);
        
    }
...

Другими словами, рекурсия как бы разворачивается в обратную сторону. Думаю, суть вы поняли.

Добавлено через 2 минуты
P.S. На сколько я знаю, в java нет оптимизации хвостовой рекурсии, поэтому будьте аккуратны при глубоких вызовах.

@korvin_ · 20.04.2021, 02:35

Сообщение от Tavashi

Java
1
2
3
4
5
6
7
8
9
10
...
    private static void left(int l) {
        if (l < 2) {
            return;
        }
        System.out.printf("%d ", l);
        left(l - 1);
        System.out.printf("%d ", l);
}
...

в java нет оптимизации хвостовой рекурсии

Но эта процедура и не хвостовая.

Добавлено через 15 минут
Tavashi, вот это хвостовая:

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    private static void p(int n) {
        System.out.println("Input: " + n);
        System.out.print("Output:");
        var start = (int) Math.ceil(n/2.0);
        var even = (n & 1) == 0;
        tailrec(start, even, start, -1);
        System.out.println();
    }
 
    private static void tailrec(int start, boolean even, int current, int step) {
        if (current > start) {
            return;
        }
        System.out.print(" " + current);
        if (current > 1) {
            tailrec(start, even, current+step, step);
        } else {
            if (even) { System.out.print(" " + current); }
            tailrec(start, even, current+1, 1);
        }
    }

— https://ideone.com/3L8K9C

Впрочем, в Java нет TCO, да.

@Tavashi · 20.04.2021, 03:31

Сообщение от korvin_

Но эта процедура и не хвостовая.

Спасибо, но я не вижу где бы я утверждал обратное.

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

P.S. Точно сейчас не вспомню, но где-то читал, что должны были завести ОХР в новых версиях чашки.

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение Это мой обзор планшета X220 с точки зрения школьника. Недавно я решила попытаться уменьшить свой. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

Задача с рекурсией

Решение

Решение

@Nahmir 0 / 0 / 0 Регистрация: 06.04.2021 Сообщений: 9
	19.04.2021, 23:09 [ТС]
	Мы сейчас проходим тему рекурсии, поэтому эта задача должна делаться именно через рекурсию 0

@xoraxax 3639 / 2971 / 918 Регистрация: 05.07.2013 Сообщений: 14,220
	19.04.2021, 23:12
	Сразу вперёд и назад добавляй число. 1, 212, 32123... 0