Задача из книги "Структура и интерпретация компьютерных программ"

@Vovsla · Регистрация: 19.09.2018

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

В книге дается вот такая задача

JavaScript
1
2
3
4
5
6
7
8
9
function A(x, y) {
    return y === 0
    ? 0
    : x === 0
    ? 2 * y
    : y === 1
    ? 2
    : A(x - 1, A(x, y - 1));
}

и к ней вопрос, каковы значения следующих выражений:

JavaScript
1
2
3
A (1, 10)
A (2, 4)
A (3, 3)

С короткой записью условного оператора я ознакомился, но не понятно как это можно легко посчитать в уме?
У меня node.js выдает результаты:
1024
65536
65536

У меня такое ощущение, что я чего-то не понимаю, но не пойму чего

@DrType · 17.02.2023, 21:22

Не по теме:

Переедем в JavaScript для начинающих , т. к. данный скрипт будет так же выполняться и в браузере.

krvsa · 17.02.2023, 22:27

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

но не понятно как это можно легко посчитать в уме?

Ты не одинок в этом вопросе...

У нас про одного препода шутили - все самые сложные моменты его лекций начинались после слов "Ясно что ..." или "Совершенно очевидно что ...".

@xkkx · 17.02.2023, 22:40

Как же хорошо что, в PHP у разработчиков хватило ума бить по рукам людей дубиной, которые не умеют ставить скобки)

@DrType · 17.02.2023, 22:50

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

Как же хорошо что, в PHP у разработчиков хватило ума бить по рукам людей дубиной, которые не умеют ставить скобки)

Хотел предложить ТС для начала отформатировать код) А форматтер можно настроить так, чтобы расставлял скобки как надо...

@xkkx · 17.02.2023, 23:04

Code
1
A (1, 10)

Кликните здесь для просмотра всего текста

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2)) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3)) = 16
x === 0 = 2*y = 32
A(x - 1 = 0, A(x=1, y-1=4)) = 32
x === 0 = 2*y = 64
A(x - 1 = 0, A(x=1, y-1=5)) = 64
x === 0 = 2*y = 128
A(x - 1 = 0, A(x=1, y-1=6)) = 128
x === 0 = 2*y = 256
A(x - 1 = 0, A(x=1, y-1=7)) = 256
x === 0 = 2*y = 512
A(x - 1 = 0, A(x=1, y-1=8)) = 512
x === 0 = 2*y = 1024
A(x - 1 = 0, A(x=1, y-1=9)) = 1024

Code
1
A (2, 4)

Кликните здесь для просмотра всего текста

Code
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
y === 1 = 2
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4
A(x - 1 = 1, A(x=2, y-1=1)) = 4
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2)) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3)) = 16
A(x - 1 = 1, A(x=2, y-1=2)) = 16
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2)) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3)) = 16
x === 0 = 2*y = 32
A(x - 1 = 0, A(x=1, y-1=4)) = 32
x === 0 = 2*y = 64
A(x - 1 = 0, A(x=1, y-1=5)) = 64
x === 0 = 2*y = 128
A(x - 1 = 0, A(x=1, y-1=6)) = 128
x === 0 = 2*y = 256
A(x - 1 = 0, A(x=1, y-1=7)) = 256
x === 0 = 2*y = 512
A(x - 1 = 0, A(x=1, y-1=8)) = 512
x === 0 = 2*y = 1024
A(x - 1 = 0, A(x=1, y-1=9)) = 1024
x === 0 = 2*y = 2048
A(x - 1 = 0, A(x=1, y-1=10)) = 2048
x === 0 = 2*y = 4096
A(x - 1 = 0, A(x=1, y-1=11)) = 4096
x === 0 = 2*y = 8192
A(x - 1 = 0, A(x=1, y-1=12)) = 8192
x === 0 = 2*y = 16384
A(x - 1 = 0, A(x=1, y-1=13)) = 16384
x === 0 = 2*y = 32768
A(x - 1 = 0, A(x=1, y-1=14)) = 32768
x === 0 = 2*y = 65536
A(x - 1 = 0, A(x=1, y-1=15)) = 65536
A(x - 1 = 1, A(x=2, y-1=3)) = 65536

Code
1
A (3, 3)

Кликните здесь для просмотра всего текста

Code
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
y === 1 = 2
y === 1 = 2
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4
A(x - 1 = 1, A(x=2, y-1=1)) = 4
A(x - 1 = 2, A(x=3, y-1=1)) = 4
y === 1 = 2
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4
A(x - 1 = 1, A(x=2, y-1=1)) = 4
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2)) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3)) = 16
A(x - 1 = 1, A(x=2, y-1=2)) = 16
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2)) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3)) = 16
x === 0 = 2*y = 32
A(x - 1 = 0, A(x=1, y-1=4)) = 32
x === 0 = 2*y = 64
A(x - 1 = 0, A(x=1, y-1=5)) = 64
x === 0 = 2*y = 128
A(x - 1 = 0, A(x=1, y-1=6)) = 128
x === 0 = 2*y = 256
A(x - 1 = 0, A(x=1, y-1=7)) = 256
x === 0 = 2*y = 512
A(x - 1 = 0, A(x=1, y-1=8)) = 512
x === 0 = 2*y = 1024
A(x - 1 = 0, A(x=1, y-1=9)) = 1024
x === 0 = 2*y = 2048
A(x - 1 = 0, A(x=1, y-1=10)) = 2048
x === 0 = 2*y = 4096
A(x - 1 = 0, A(x=1, y-1=11)) = 4096
x === 0 = 2*y = 8192
A(x - 1 = 0, A(x=1, y-1=12)) = 8192
x === 0 = 2*y = 16384
A(x - 1 = 0, A(x=1, y-1=13)) = 16384
x === 0 = 2*y = 32768
A(x - 1 = 0, A(x=1, y-1=14)) = 32768
x === 0 = 2*y = 65536
A(x - 1 = 0, A(x=1, y-1=15)) = 65536
A(x - 1 = 1, A(x=2, y-1=3)) = 65536
A(x - 1 = 2, A(x=3, y-1=2)) = 65536

Добавлено через 1 минуту
Пересчитал, немного ошибся. Поправил

@Vovsla · 20.02.2023, 16:18 **[ТС]**

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

Хотел предложить ТС для начала отформатировать код) А форматтер можно настроить так, чтобы расставлял скобки как надо...

Я специально оставил код в том виде, в котором он дан в учебнике

Добавлено через 9 минут

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

A (1, 10)

Почему при данном условии первая строчка "y === 1 = 2" ?

JavaScript
1
2
3
4
5
6
function A(x, y) {
    return y === 0 ? 0 :
    x === 0 ? 2 * y :
    y === 1 ? 2 :
    A(x - 1, A(x, y - 1))
}

Как я понял, запись "y === 0 ? 0 : x" означает - если Y равен 0, то вернуть 0, иначе вернуть X.

@xkkx · 20.02.2023, 16:32

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

Почему при данном условии первая строчка "y === 1 = 2" ?

Code
1
2
3
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4

Читается с права на лево. Т-е происходит вызов сначала "A(x=1, y-1=1)" Потом происходит вызов A(x - 1 = 0, 2) = 4.

А второй параметр y-1=1 у нас как раз 1 от этого первая строкаа "y === 1 = 2"

Добавлено через 8 минут
1, 10

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1) = 2) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2) = 4) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3) = 8) = 16
x === 0 = 2*y = 32
A(x - 1 = 0, A(x=1, y-1=4) = 16) = 32
x === 0 = 2*y = 64
A(x - 1 = 0, A(x=1, y-1=5) = 32) = 64
x === 0 = 2*y = 128
A(x - 1 = 0, A(x=1, y-1=6) = 64) = 128
x === 0 = 2*y = 256
A(x - 1 = 0, A(x=1, y-1=7) = 128) = 256
x === 0 = 2*y = 512
A(x - 1 = 0, A(x=1, y-1=8) = 256) = 512
x === 0 = 2*y = 1024
A(x - 1 = 0, A(x=1, y-1=9) = 512) = 1024

2,4

Кликните здесь для просмотра всего текста

Code
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
y === 1 = 2
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1) = 2) = 4
A(x - 1 = 1, A(x=2, y-1=1) = 2) = 4
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1) = 2) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2) = 4) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3) = 8) = 16
A(x - 1 = 1, A(x=2, y-1=2) = 4) = 16
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1) = 2) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2) = 4) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3) = 8) = 16
x === 0 = 2*y = 32
A(x - 1 = 0, A(x=1, y-1=4) = 16) = 32
x === 0 = 2*y = 64
A(x - 1 = 0, A(x=1, y-1=5) = 32) = 64
x === 0 = 2*y = 128
A(x - 1 = 0, A(x=1, y-1=6) = 64) = 128
x === 0 = 2*y = 256
A(x - 1 = 0, A(x=1, y-1=7) = 128) = 256
x === 0 = 2*y = 512
A(x - 1 = 0, A(x=1, y-1=8) = 256) = 512
x === 0 = 2*y = 1024
A(x - 1 = 0, A(x=1, y-1=9) = 512) = 1024
x === 0 = 2*y = 2048
A(x - 1 = 0, A(x=1, y-1=10) = 1024) = 2048
x === 0 = 2*y = 4096
A(x - 1 = 0, A(x=1, y-1=11) = 2048) = 4096
x === 0 = 2*y = 8192
A(x - 1 = 0, A(x=1, y-1=12) = 4096) = 8192
x === 0 = 2*y = 16384
A(x - 1 = 0, A(x=1, y-1=13) = 8192) = 16384
x === 0 = 2*y = 32768
A(x - 1 = 0, A(x=1, y-1=14) = 16384) = 32768
x === 0 = 2*y = 65536
A(x - 1 = 0, A(x=1, y-1=15) = 32768) = 65536
A(x - 1 = 1, A(x=2, y-1=3) = 16) = 65536

3, 3

Кликните здесь для просмотра всего текста

Code
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
y === 1 = 2
y === 1 = 2
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1) = 2) = 4
A(x - 1 = 1, A(x=2, y-1=1) = 2) = 4
A(x - 1 = 2, A(x=3, y-1=1) = 2) = 4
y === 1 = 2
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1) = 2) = 4
A(x - 1 = 1, A(x=2, y-1=1) = 2) = 4
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1) = 2) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2) = 4) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3) = 8) = 16
A(x - 1 = 1, A(x=2, y-1=2) = 4) = 16
y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1) = 2) = 4
x === 0 = 2*y = 8
A(x - 1 = 0, A(x=1, y-1=2) = 4) = 8
x === 0 = 2*y = 16
A(x - 1 = 0, A(x=1, y-1=3) = 8) = 16
x === 0 = 2*y = 32
A(x - 1 = 0, A(x=1, y-1=4) = 16) = 32
x === 0 = 2*y = 64
A(x - 1 = 0, A(x=1, y-1=5) = 32) = 64
x === 0 = 2*y = 128
A(x - 1 = 0, A(x=1, y-1=6) = 64) = 128
x === 0 = 2*y = 256
A(x - 1 = 0, A(x=1, y-1=7) = 128) = 256
x === 0 = 2*y = 512
A(x - 1 = 0, A(x=1, y-1=8) = 256) = 512
x === 0 = 2*y = 1024
A(x - 1 = 0, A(x=1, y-1=9) = 512) = 1024
x === 0 = 2*y = 2048
A(x - 1 = 0, A(x=1, y-1=10) = 1024) = 2048
x === 0 = 2*y = 4096
A(x - 1 = 0, A(x=1, y-1=11) = 2048) = 4096
x === 0 = 2*y = 8192
A(x - 1 = 0, A(x=1, y-1=12) = 4096) = 8192
x === 0 = 2*y = 16384
A(x - 1 = 0, A(x=1, y-1=13) = 8192) = 16384
x === 0 = 2*y = 32768
A(x - 1 = 0, A(x=1, y-1=14) = 16384) = 32768
x === 0 = 2*y = 65536
A(x - 1 = 0, A(x=1, y-1=15) = 32768) = 65536
A(x - 1 = 1, A(x=2, y-1=3) = 16) = 65536
A(x - 1 = 2, A(x=3, y-1=2) = 4) = 65536

Добавлено через 1 минуту
Вот так по лучше вроде для понимания

Добавлено через 13 секунд
А то сам запутался)

@Vovsla · 21.02.2023, 10:40 **[ТС]**

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

Читается с права на лево. Т-е происходит вызов сначала "A(x=1, y-1=1)" Потом происходит вызов A(x - 1 = 0, 2) = 4.
А второй параметр y-1=1 у нас как раз 1 от этого первая строка "y === 1 = 2"

Почему "y-1=1" если в качестве "y" передается 10?

@xkkx · 21.02.2023, 13:23

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

Почему "y-1=1" если в качестве "y" передается 10?

А почему должно быть 10 (9)? По какой такой логике. У нас внутренние вызовы разворачивают для 10 ответ в виде 1024. Логично что сначала будет в порядке возрастания.

@Vovsla · 21.02.2023, 22:29 **[ТС]**

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

А почему должно быть 10 (9)?

Функцию А можно вызвать с двумя аргументами. И в вызове A (1, 10) передается 2 аргумента: 1 и 10.
И внутри функции X = 1, а Y = 10 как на последней строчке.

Или так просто показана рекурсия, а по факту вычисление идет
Изначальный вызов: A (1, 10)
A(x, y - 1) - A(1, 9) - положили в буфер
A(x, y - 1) - A(1, 8) - положили в буфер
A(x, y - 1) - A(1, 7) - положили в буфер
A(x, y - 1) - A(1, 6) - положили в буфер
A(x, y - 1) - A(1, 5) - положили в буфер
A(x, y - 1) - A(1, 4) - положили в буфер
A(x, y - 1) - A(1, 3) - положили в буфер
A(x, y - 1) - A(1, 2) - положили в буфер

A(1, 1) - вызов со срабатыванием условия y === 1 при котором возвращается 2 во внутреннем выражении A(x - 1, A(x, y - 1)), что приводит к вызову A(0, 2), который в свою очередь приводит к срабатыванию условия x === 0, что приводит к возврату значения 2 * y и рекурсия начинает разматываться в обратном порядке
2 * 2 = 4
4 * 2 = 8
8 * 2 = 16
16 * 2 = 32
32 * 2 = 64
64 * 2 = 128
128 * 2 = 256
256 * 2 = 512
512 * 2 = 1024

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

y === 1 = 2
x === 0 = 2*y = 4
A(x - 1 = 0, A(x=1, y-1=1)) = 4
Читается с права на лево. Т-е происходит вызов сначала "A(x=1, y-1=1)" Потом происходит вызов A(x - 1 = 0, 2) = 4.

Сначала не могу понять почему вдруг справа на лево, потом понял, что суть не в направлении, а в первичном вычислении вложенного выражения

@xkkx · 21.02.2023, 22:36

Ну тут в принципе ничего сложного. Сложнее объяснить человеку

Но сама по себе функция с рекурсией очень лёгенькая, в особенности если вы уберёте тернарный оператор хотя бы мысленно.

Новые блоги и статьи Все статьи Все блоги /
Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .	Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .

@DrType
	17.02.2023, 21:22
	Не по теме: Переедем в JavaScript для начинающих , т. к. данный скрипт будет так же выполняться и в браузере. 0

@xkkx 132 / 76 / 16 Регистрация: 08.07.2022 Сообщений: 309
	17.02.2023, 22:40
	Как же хорошо что, в PHP у разработчиков хватило ума бить по рукам людей дубиной, которые не умеют ставить скобки) 0

@xkkx 132 / 76 / 16 Регистрация: 08.07.2022 Сообщений: 309
	21.02.2023, 22:36
	Ну тут в принципе ничего сложного. Сложнее объяснить человеку Но сама по себе функция с рекурсией очень лёгенькая, в особенности если вы уберёте тернарный оператор хотя бы мысленно. 1