Решение задач с использованием рекурсии

echs · Регистрация: 23.10.2013

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

Когда я обратился к поисковой системе, то я не нашёл
ни одного упоминания о рекурсии. Испытав шок, я
решил создать эту тему на QBasic. (В паскале о рекурсии
говорят на каждом углу). Приведу нестандартный пример
рекурсии:
Посадил дед репку. И выросла она большая-пребольшая.
(Далее вызывается рекурсивная процедура)
Тянет дед репку, потянет, вытащить не может.
(Условием выхода из этой процедуры будет событие
при котором репка будет вытащена)
Эта процедура вызывает сама себя и на помощь деду
приходит бабка. И тд. После шестого вызова процедуры
на арене появляется мышка. Благодаря которой репку
вытаскивают. Условие окончания процедуры соблюдено
и программа (как и сказка) завершается.
Что надо знать при написании рекурсивных программ.
1. Оператор CLEAR, , 29000
Этот оператор задаёт величину стека. В данном примере
приведена цифра 29000 - это максимальная величина
стека для QBasic v1.0 -1.1. Для QuickBasic стек ещё больше.
2. Функция FRE(-2) ; (PRINT FRE(-2))
Эта функция указывает (в байтах) свободное стековое
пространство.
3. Функция DEF FN... - эта функция не поддерживает
рекурсии.
4. Рекурсию поддерживают
1) FUNCTION - END FUNCTION
2) SUB - END SUB
3) GOSUB - RETURN
Последним правда не слишком удобно пользоваться, но
пару примеров я приведу (именно на GOSUB - RETURN)

Эта программа вычисляет сумму n натуральных чисел

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CLS
CLEAR, , 20000
INPUT "N = "; N
 
GOSUB RECURSIA
PRINT Sum
END
 
RECURSIA:
IF n > 0 THEN
   Sum = Sum +n
   n = n - 1
   GOSUB RECURSIA
END IF
RETURN

Добавлено через 10 часов 46 минут
Это программа вычисляет числа Фибоначи

QBasic/QuickBASIC
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
DECLARE FUNCTION SSTR(n!)
CLS
DEFLNG F
CLEAR, , 10000
 
INPUT "N = "; n
m = n
f1 = 1: f2 = 1: fi = 1
 
GOSUB RECURSIA
 
PRINT " fi(" + SSTR(m) + ") ="; fi
END
 
RECURSIA:
IF n = 1 OR n = 2 THEN
   RETURN
ELSE
   fi = f1 + f2
   f1 = f2
   f2 = fi
   n = n - 1
   GOSUB RECURSIA
END IF
RETURN
 
FUNCTION SSTR(n)
   SSTR = LTRIM$(STR$(n))
END FUNCTION

@Sasha_Smirnov · 07.08.2015, 23:31

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

программируют в основном

программисты (в т. ч. любители) да фрилансеры.

Школьники же (кроме необычно усидчивых) подходят так:

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

Сообщение от Эсмиральда

можешь загуглить

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

QBasic/QuickBASIC
1
REM * Этот красивый пример смешанной рекурсии

Да, на редкость красиво! Или я давно не читал эту ветвь.

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

QBasic/QuickBASIC
1
2
REM *Дан массив A() из 10 целых чисел
REM *Определить максимальный элемент A()

Для сравнения: 2-й максимум (правда, без рекурсии): Дан целочисленный массив размером N. Определить значение второго по величине элемента массива

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

этого никто не поймёт

Тут — найдутся! Вот, например, как мистер KoGG в соседней ветке Авторские программы, библиотеки, надстройки и шаблоны довёл мои геометрические художества 2007 года [исходник приложен; код по альт-F11] до высот мастерства: https://www.cyberforum.ru/atta... 1381491070

@CoderHuligan · 11.08.2015, 13:25

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

Программа запрашивает ввод чисел
REM * * * * (0 - конец ввода)
REM *И выводит эти числа на экран
REM * * * *в обратном порядке.

geh, программа не работает. Что-то тут пропущено в коде, наверное.

echs · 19.08.2015, 12:29 **[ТС]**

Я проверил эту программу. Она работает.
Вы уверены, что у вас QBasic?

@CoderHuligan · 20.08.2015, 12:15

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

Вы уверены, что у вас QBasic?

Программы я тестирую в free basic в режиме #lang "qb". И к вашей чести ваши программы работают прекрасно даже с исключённой из программы строчкой : CLEAR , , 20000, так как на работу программы на современных системах она не влияет.
Я имею ввиду вот эту конкретно программу:

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
DECLARE SUB FOX ()
 
CLS
CLEAR , , 20000
CALL FOX
END
 
SUB FOX
DIM n  AS INTEGER
   INPUT n
   IF n THEN CALL FOX
   IF n THEN PRINT n;
END SUB

Она должна по идее менять числа на противоположенный порядок. Может быть из-за того что я исключил ту строчку? Вряд ли. Другие-то программы без этой строки работают. Вроде и здесь стек, и там стек... Хотя возможно что в dos всё по другому.

Добавлено через 18 минут
То есть эту программу уже трудно будет переписать на другой язык, так как здесь видимо использована особенность конкретной системы.

@locm · 20.08.2015, 12:29

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

эту программу уже трудно будет переписать на другой язык

Переписал на PB. Числа местами меняет.

@CoderHuligan · 20.08.2015, 14:21

Всё понял! Надо было вводить цифры последовательно одну за другой, а не строкой! Теперь всё работает! К сожалению этот момент не был очевиден с самого начала. Извините geh.

@locm · 20.08.2015, 15:07

Не по теме:

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

этот момент не был очевиден с самого начала

По моему это очевидно смотря на код.

@CoderHuligan · 20.08.2015, 16:21

Бывает и не такое...

echs · 23.10.2015, 10:04 **[ТС]**

В этой программе показан пример применения семи функций
f1 вызывает функцию f2
f2 вызывает функцию f3
......
f6 вызывает функцию f7
f7 вызывает функцию f1
Рекурсия налицо. Это длинная цепь так называемой косвенной рекурсии.

QBasic/QuickBASIC
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
REM    РЕКУРСИВНАЯ ЦЕПЬ
REM    f1 => f2 => ... => f7 => f1
 
DECLARE SUB f7 ()
DECLARE SUB f6 ()
DECLARE SUB f5 ()
DECLARE SUB f4 ()
DECLARE SUB f3 ()
DECLARE SUB f2 ()
DECLARE SUB f1 ()
 
RANDOMIZE TIMER
CLS
DEFLNG A-Z
 
DIM SHARED s
DIM SHARED n
 
CLEAR , , 20000
 
CALL f1
 
PRINT "S ="; s
PRINT "N ="; n
END
 
SUB f1
DIM m AS LONG
   m = 31 * RND
   IF m THEN
      CALL f2
      s = s + m
      n = n + 1
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f2
DIM m AS LONG
   m = 32 * RND
   IF m THEN
      CALL f3
      s = s + m
      n = n + 1
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f3
DIM m AS LONG
   m = 33 * RND
   IF m THEN
      CALL f4
      s = s + m
      n = n + 1
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f4
DIM m AS LONG
   m = 34 * RND
   IF m THEN
      CALL f5
      s = s + m
      n = n + 1
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f5
DIM m AS LONG
   m = 35 * RND
   IF m THEN
      CALL f6
      s = s + m
      n = n + 1
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f6
DIM m AS LONG
   m = 36 * RND
   IF m THEN
      CALL f7
      s = s + m
      n = n + 1
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f7
DIM m AS LONG
   m = 37 * RND
   IF m THEN
      CALL f1
      s = s + m
      n = n + 1
   ELSE
      EXIT SUB
   END IF
END SUB

Удачи всем!

@Sasha_Smirnov · 23.10.2015, 16:43

Просто мини-сценарий пьесы Островского «У семи нянек…»!

Не на чем проверить (комп не мой), но дитя у них, хочется верить, с глазом!

echs · 23.10.2015, 17:07 **[ТС]**

Sasha_Smirnov,
Я не просто так написал эту программу. А дальним прицелом.
Ведь таким способом можно вести многочлен переменной длины. Представляет, вы водите лишь число (степень многочлена). Далее он вычислиться сам по цепочке.

echs · 24.10.2015, 13:18 **[ТС]**

Программа рисует.

QBasic/QuickBASIC
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
REM Программа рисует узор
 
DECLARE SUB f (x!, y!, r!, p!, q!)
 
CLS
CLEAR , , 20000
SCREEN 11
WINDOW (-320, 240)-(320, -240)
 
CALL f(0, 0, 100, 3, 4)
 
PRINT "Press Enter"
SLEEP 0
SCREEN 0
END
 
SUB f (x, y, r, p, q)
   IF p > 0 THEN
      s = r - 1
      LINE (x - r, y + r)-(x + r, y - r), , B
      LINE (x - s, y + s)-(x + s, y - s), 0, BF
      FOR i = 1 TO 30000: NEXT
      CALL f(x, y, r / q, p - 1, q)
      CALL f(x + r, y, r / q, p - 1, q)
      CALL f(x + r, y + r, r / q, p - 1, q)
      CALL f(x, y + r, r / q, p - 1, q)
      CALL f(x - r, y + r, r / q, p - 1, q)
      CALL f(x - r, y, r / q, p - 1, q)
      CALL f(x - r, y - r, r / q, p - 1, q)
      CALL f(x, y - r, r / q, p - 1, q)
      CALL f(x + r, y - r, r / q, p - 1, q)
   END IF
END SUB

echs · 24.10.2015, 13:21 **[ТС]**

Изменяя параметр q - получим разные рисунки
Попробуйте! И подивитесь!

echs · 26.10.2015, 09:57 **[ТС]**

Красивая программа, реализующая вычисление
полинома переменной длины.

QBasic/QuickBASIC
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
REM    Вычисление полинома переменной длины. 
REM    Программа запрашивает длину полинома
REM     (число N) и значение переменной Х.
REM    Коэффициенты заданы в операторе DATA
REM    Алгоритм представляет собой рекурсивную
REM    цепь        f1 => f2 => ... => f7 => f1
 
DECLARE SUB f1 ()
DECLARE SUB f2 ()
DECLARE SUB f3 ()
DECLARE SUB f4 ()
DECLARE SUB f5 ()
DECLARE SUB f6 ()
DECLARE SUB f7 ()
 
CLS
REM      POLINOM
REM a7*X^7 + a6*X^6 + ... + a0
 
DATA 1,2,3,4,5,6,7,8 
 
DIM SHARED y
DIM SHARED x
DIM SHARED n
DIM SHARED a(7)
 
CLEAR , , 20000
PRINT "1<= N <=7"
INPUT "N,X = "; n, x
 
FOR i = 7 TO 0 STEP -1
   READ a(i)
NEXT i
 
y = a(0)
 
CALL f1
 
PRINT "Y ="; y
END
 
SUB f1
   IF n THEN
      y = y + a(1) * x
      n = n - 1
      CALL f2
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f2
   IF n THEN
      y = y + a(2) * x ^ 2
      n = n - 1
      CALL f3
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f3
   IF n THEN
      y = y + a(3) * x ^ 3
      n = n - 1
      CALL f4
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f4
   IF n THEN
      y = y + a(4) * x ^ 4
      n = n - 1
      CALL f5
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f5
   IF n THEN
      y = y + a(5) * x ^ 5
      n = n - 1
      CALL f6
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f6
   IF n THEN
      y = y + a(6) * x ^ 6
      n = n - 1
      CALL f7
   ELSE
      EXIT SUB
   END IF
END SUB
 
SUB f7
   IF n THEN
      y = y + a(7) * x ^ 7
      n = n - 1
      CALL f1
   ELSE
      EXIT SUB
   END IF
END SUB

echs · 13.11.2015, 13:46 **[ТС]**

Программа рисует узор

QBasic/QuickBASIC
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
DECLARE SUB Quad (n!, a!)
 
CLS
CLEAR , , 2000
DIM SHARED f
DIM SHARED k
f = .15708
k = 1 / (SIN(f) + COS(f))
 
SCREEN 11
WINDOW (0, 0)-(640, 480)
 
CALL Quad(10, 600)
 
PRINT "Press Enter"
SLEEP 0
SCREEN 0
END
 
DEFSNG S, X-Z
SUB Quad (n, a)
   IF n >= 0 THEN
      x = a * COS(n * f) * k ^ n + 320
      y = a * SIN(n * f) * k ^ n + 240
      x2 = 640 - x
      y2 = 480 - y
      LINE (x, y)-(x2, y2), 1, B
 
      FOR j& = 1 TO 700000: NEXT j&
 
      CALL Quad(n - 1, .885 * a)
   END IF
END SUB

echs · 13.11.2015, 17:22 **[ТС]**

Программа рисует вписанные друг в друга квадраты,
повернутые на 9° (11 квадратов)

QBasic/QuickBASIC
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
DECLARE SUB Quad (n!)
 
CLS
CLEAR , , 2000
CONST pi2 = 1.5708
DIM SHARED f
DIM SHARED k
f = .15708
k = 1 / (SIN(f) + COS(f))
 
SCREEN 11
WINDOW (-40, 30)-(40, -30)
 
CALL Quad(20)
 
PRINT "Press Enter"
SLEEP 0
SCREEN 0
END
 
SUB Quad (n)
   IF n >= 0 THEN
      x = 20 * COS(n * f) * k ^ n
      y = 20 * SIN(n * f) * k ^ n
      x2 = 20 * COS(n * f + pi2) * k ^ n
      y2 = 20 * SIN(n * f + pi2) * k ^ n
 
      LINE (x, y)-(x2, y2), 1
      LINE (x2, y2)-(-x, -y), 1
      LINE (-x, -y)-(-x2, -y2), 1
      LINE (-x2, -y2)-(x, y), 1
 
      FOR j& = 1 TO 700000: NEXT j&
 
      CALL Quad(n - 1)
   END IF
END SUB

@Catstail · 15.11.2015, 10:55

geh, с огромным интересом прочитал тему! Спасибо! Хотел только добавить одно простое соображение: рекурсию следует применять в том случае, когда структура данных рекурсивна (напр. дерево поиска). Применение рекурсии в остальных случаях - дело вкуса. Еще был разговор о быстрой сортировке - ее нерекурсивный вариант рассматривался в этой нити

echs · 15.11.2015, 11:19 **[ТС]**

Catstail, Спасибо!
Я в этой теме ставил задачей показать, как вообще
применять рекурсию. Это мало кто знает и я целый
год ей занимался. Этому нигде не учат. Многие вообще
не знают о рекурсии. Эта тема мини пособие по рекурсии.

@Catstail · 15.11.2015, 11:25

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

Этому нигде не учат. Многие вообще
не знают о рекурсии.

- то, что "этому нигде не учат" - сильно сказано. Есть языки, в которых без рекурсии просто делать нечего (Лисп, Пролог, Хаскелл, F#, OCaml...) Загляните в соотв. разделы Форума и убедитесь.

echs · 16.11.2015, 18:32 **[ТС]**

В теории групп есть группа подстановок.
Каждый элемент этой группы может быть представлен
как произведение транспозиций. Эта про и вычисляет их
количество.

QBasic/QuickBASIC
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
48
49
50
51
52
53
54
REM  Задан массив А(), состоящий из рандомно
REM  переставленных чисел 1, 2, 3, ... , 10
REM  Программа определяет количество транспозиций,
REM  приводящих этот массив в порядок 1, 2, ... , 10
 
DECLARE FUNCTION CH% (a() AS INTEGER, n%)
 
CLS
RANDOMIZE TIMER
DIM SHARED p AS INTEGER
DIM n AS INTEGER
DIM j AS INTEGER
CLEAR , , 20000
 
n = 10
DIM a(1 TO n) AS INTEGER
 
FOR i = 1 TO n
   a(i) = i
NEXT i
 
FOR i = 1 TO n
   j = 10 * RND + .5
   SWAP a(i), a(j)
NEXT i
 
FOR i = 1 TO n
   PRINT a(i);
NEXT i: PRINT : PRINT
 
PRINT "     TRANSPOSICIY ="; CH(a(), n)
PRINT
 
FOR i = 1 TO n
   PRINT a(i);
NEXT i: PRINT
 
END
 
FUNCTION CH% (a() AS INTEGER, n AS INTEGER)
  
   IF n = 1 THEN
      CH = p
   ELSE
      FOR i = 1 TO n - 1
         IF a(i) = n THEN
            SWAP a(i), a(n)
            p = p + 1
            EXIT FOR
         END IF
      NEXT i
      CH = CH(a(), n - 1)
   END IF
END FUNCTION

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	19.08.2015, 12:29 [ТС]
	Я проверил эту программу. Она работает. Вы уверены, что у вас QBasic? 0

@CoderHuligan 1753 / 1019 / 257 Регистрация: 30.06.2015 Сообщений: 5,132 Записей в блоге: 56
	20.08.2015, 14:21
	Всё понял! Надо было вводить цифры последовательно одну за другой, а не строкой! Теперь всё работает! К сожалению этот момент не был очевиден с самого начала. Извините geh. 0

@CoderHuligan 1753 / 1019 / 257 Регистрация: 30.06.2015 Сообщений: 5,132 Записей в блоге: 56
	20.08.2015, 16:21
	Бывает и не такое... 0

@Sasha_Smirnov 5562 / 1370 / 150 Регистрация: 08.02.2009 Сообщений: 4,109 Записей в блоге: 30
	23.10.2015, 16:43
	Просто мини-сценарий пьесы Островского «У семи нянек…»! Не на чем проверить (комп не мой), но дитя у них, хочется верить, с глазом! 1

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	23.10.2015, 17:07 [ТС]
	Sasha_Smirnov, Я не просто так написал эту программу. А дальним прицелом. Ведь таким способом можно вести многочлен переменной длины. Представляет, вы водите лишь число (степень многочлена). Далее он вычислиться сам по цепочке. 0

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	24.10.2015, 13:21 [ТС]
	Изменяя параметр q - получим разные рисунки Попробуйте! И подивитесь! 0

@Catstail Супер-модератор 38210 / 21143 / 4313 Регистрация: 12.02.2012 Сообщений: 34,756 Записей в блоге: 14
	15.11.2015, 10:55
	geh, с огромным интересом прочитал тему! Спасибо! Хотел только добавить одно простое соображение: рекурсию следует применять в том случае, когда структура данных рекурсивна (напр. дерево поиска). Применение рекурсии в остальных случаях - дело вкуса. Еще был разговор о быстрой сортировке - ее нерекурсивный вариант рассматривался в этой нити 2

echs Регистрация: 23.10.2013 Сообщений: 5,076 Записей в блоге: 8
	15.11.2015, 11:19 [ТС]
	Catstail, Спасибо! Я в этой теме ставил задачей показать, как вообще применять рекурсию. Это мало кто знает и я целый год ей занимался. Этому нигде не учат. Многие вообще не знают о рекурсии. Эта тема мини пособие по рекурсии. 0