Рекурсия

Описание	Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя. В программировании чаще всего - вызов функцией себя самой, когда функция (процедура) делегирует работу своим клонам
Область знаний	Информатика
Авторы	Brian Harvey
Поясняющее видео	https://www.youtube.com/watch?v=eiGHdT6lydA
Близкие понятия	Клон, Процедура, Фрактал
Среды и средства для освоения понятия	Лого, 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.

Вычисление факториала

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])

Построение фракталов

• Треугольник Серпинского
• https://en.scratch-wiki.info/wiki/Recursion_and_Fractals
  • https://scratch.mit.edu/projects/10068174/

Теория

Процедуры и функции. Как создаются и как используются пользовательские функции. Процедуры как средство абстракции.

Практика

Какие блоки используются для создания собственных процедур в Scratch? Создайте процедуру, которая будет принимать на входе три числа и присваивать переменной значение наибольшего из этих трех чисел.

Примеры рекурсии в Snap!

Построение деревьев

Построение дерева

Скрипт (изображение)	Проект