Рекурсия: различия между версиями
Материал из Поле цифровой дидактики
Patarakin (обсуждение | вклад) |
Patarakin (обсуждение | вклад) |
||
(не показано 19 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
<center>[[Файл:Alg video 04 recursion.png|400px]]</center> | |||
{{Понятие | {{Понятие | ||
|Description=Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. | |Description=Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. | ||
В программировании чаще всего - вызов функцией себя самой, когда функция (процедура) делегирует работу своим | В программировании чаще всего - вызов функцией себя самой, когда функция (процедура) делегирует работу своим клонам. | ||
http://digida.mgpu.ru/images/thumb/7/7c/Factorial_rus.png/400px-Factorial_rus.png | |||
|Field_of_knowledge=Информатика | |Field_of_knowledge=Информатика | ||
|Inventor=Brian Harvey | |||
|Clarifying_video=https://www.youtube.com/watch?v=eiGHdT6lydA | |||
|similar_concepts=клон, процедура, Фрактал | |||
|Environment=Lisp, Лого, Scratch, Snap!, Scheme, Lua, Python, РЕФАЛ | |||
|FieldActivity=Computational Thinker | |FieldActivity=Computational Thinker | ||
|Возрастная категория=11 | |Возрастная категория=11 | ||
}} | }} | ||
=== Примеры === | === Примеры === | ||
Введение в рекурсию в книге Харви о стиле Лого - http://people.eecs.berkeley.edu/~bh/v1ch7/recur1.html | def fact( x): | ||
if x = = 1: | |||
return 1 | |||
else: | |||
return x * fact( x-1) | |||
[[Файл:Factorial rus.png|400px]] | |||
Введение в рекурсию в книге Харви о стиле [[Лого]] - http://people.eecs.berkeley.edu/~bh/v1ch7/recur1.html | |||
to spiral :size | |||
if :size > 30 [stop] ; an exit condition | |||
fd :size rt 15 ; many lines of action | |||
spiral :size *1.02 ; the tailend recursive call | |||
end | |||
spiral 10 | |||
When you're thinking about a recursive procedure, it's especially important to remember that each invocation of a procedure has its own local variables. It's possible to get confused about this because, of course, if a procedure invokes itself as a subprocedure, each invocation uses the same names for local variables. For example, each invocation of downup has a local variable (its input) named word. But each invocation has a separate input variable. | When you're thinking about a recursive procedure, it's especially important to remember that each invocation of a procedure has its own local variables. It's possible to get confused about this because, of course, if a procedure invokes itself as a subprocedure, each invocation uses the same names for local variables. For example, each invocation of downup has a local variable (its input) named word. But each invocation has a separate input variable. | ||
; Маленькие человечки: How Recursion Works В книге Simple Scheme | ; Маленькие человечки: How Recursion Works В книге Simple [[Scheme]] | ||
: The crowning achievement of the little-people model is explaining recursion. Remember that every time you call a procedure, a little person is hired to compute the result. If you want to know (+ 2 (+ 3 4)), there are two separate plus specialists involved. | : The crowning achievement of the little-people model is explaining recursion. Remember that every time you call a procedure, a little person is hired to compute the result. If you want to know (+ 2 (+ 3 4)), there are two separate plus specialists involved. | ||
==== BJC Lecture 9: Recursion ==== | |||
{{#widget:YouTube|id=JKn3nsfzBdA|start=10}} | |||
==== Вычисление факториала ==== | ==== Вычисление факториала ==== | ||
Строка 38: | Строка 63: | ||
==== Построение фракталов ==== | ==== Построение фракталов ==== | ||
* [[Треугольник Серпинского]] | |||
* https://en.scratch-wiki.info/wiki/Recursion_and_Fractals | * https://en.scratch-wiki.info/wiki/Recursion_and_Fractals | ||
** https://scratch.mit.edu/projects/10068174/ | ** https://scratch.mit.edu/projects/10068174/ | ||
Строка 47: | Строка 72: | ||
: Какие блоки используются для создания собственных процедур в Scratch? Создайте процедуру, которая будет принимать на входе три числа и присваивать переменной значение наибольшего из этих трех чисел. | : Какие блоки используются для создания собственных процедур в Scratch? Создайте процедуру, которая будет принимать на входе три числа и присваивать переменной значение наибольшего из этих трех чисел. | ||
=== Примеры рекурсии в Snap! === | |||
[[Файл:Tree recursion animated script pic.png|600px]] | |||
==== Построение деревьев ==== | ==== Построение деревьев ==== | ||
Строка 57: | Строка 84: | ||
! Скрипт (изображение) !! Проект | ! Скрипт (изображение) !! Проект | ||
|- | |- | ||
| [[Файл:Tree animation script pic.png| | | [[Файл:Tree animation script pic.png| 400px]] || <snap project="tree animation" user="jens" /> | ||
|} | |} |
Текущая версия на 16:51, 23 ноября 2023
![Alg video 04 recursion.png](/images/thumb/5/59/Alg_video_04_recursion.png/400px-Alg_video_04_recursion.png)
Описание | Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.
В программировании чаще всего - вызов функцией себя самой, когда функция (процедура) делегирует работу своим клонам.
|
---|---|
Область знаний | Информатика |
Авторы | Brian Harvey |
Поясняющее видео | https://www.youtube.com/watch?v=eiGHdT6lydA |
Близкие понятия | Клон, Процедура, Фрактал |
Среды и средства для освоения понятия | Lisp, Лого, Scratch, Snap!, Scheme, Lua, Python, РЕФАЛ |
Примеры
def fact( x): if x = = 1: return 1 else: return x * fact( x-1)
Введение в рекурсию в книге Харви о стиле Лого - http://people.eecs.berkeley.edu/~bh/v1ch7/recur1.html
to spiral :size if :size > 30 [stop] ; an exit condition fd :size rt 15 ; many lines of action spiral :size *1.02 ; the tailend recursive call end spiral 10
When you're thinking about a recursive procedure, it's especially important to remember that each invocation of a procedure has its own local variables. It's possible to get confused about this because, of course, if a procedure invokes itself as a subprocedure, each invocation uses the same names for local variables. For example, each invocation of downup has a local variable (its input) named word. But each invocation has a separate input variable.
- Маленькие человечки
- How Recursion Works В книге Simple Scheme
- The crowning achievement of the little-people model is explaining recursion. Remember that every time you call a procedure, a little person is hired to compute the result. If you want to know (+ 2 (+ 3 4)), there are two separate plus specialists involved.
BJC Lecture 9: Recursion
Вычисление факториала
define factorial (n) if < (n) = [0] > then add [1] to [Factorial-stack v] else factorial ( (n) - (1) ) add ( (n) * (item (last v) of [Factorial-stack v])) to [Factorial-stack v] end when gf clicked delete (all v) of [Factorial-stack v] factorial (10) say (item (last v) of [Factorial-stack v])
Построение фракталов
- Теория
- Процедуры и функции. Как создаются и как используются пользовательские функции. Процедуры как средство абстракции.
- Практика
- Какие блоки используются для создания собственных процедур в Scratch? Создайте процедуру, которая будет принимать на входе три числа и присваивать переменной значение наибольшего из этих трех чисел.
Примеры рекурсии в Snap!
Построение деревьев
Скрипт (изображение) | Проект |
---|---|
![]() |