Рекурсия

Материал из Поле цифровой дидактики


Описание Рекурсия — определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта или процесса, то есть ситуация, когда объект является частью самого себя.

В программировании чаще всего - вызов функцией себя самой, когда функция (процедура) делегирует работу своим клонам

Область знаний Информатика
Авторы 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)

Factorial rus.png


Введение в рекурсию в книге Харви о стиле Лого - 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!

Tree recursion animated script pic.png


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

Построение дерева
Скрипт (изображение) Проект
Tree animation script pic.png