Рекурсія (програмування)

Процедура рекурсивна — процедура в програмуванні, у тілі якої знаходиться явне звернення до неї самої, або через іншу процедуру.

Застосування рекурсивних процедур, у багатьох випадках допомагає скоротити алгоритми, зробити їхню форму компактнішою.

Використання рекурсивних процедур

Рекурсивні процедури використовують, зокрема, для описання алгоритмів обчислення значень функцій, які задаються рекурентними співвідношеннями, наприклад:

• обчислення факторіалу n! = F(n): F(0) = 1; F(n) = n · F(n - 1)
• обчислення чисел Фібоначчі F(1) = F(2) = 1; F(n) = F(n - 1) + F(n - 2).

Однак, слід зазначити, що використання рекурсивних процедур пов'язане з багаторазовим входом під час виконання програми в один і той же блок без виходу із нього. Кількість рекурсивних входів називається рівнем рекурсії.

Приклад рекурсивної функції на мові програмування Python

class Node:
	def __init__(self, key, value):
		self.key = key
		self.value = value


example_of_object_to_deserialize = Node("root", [
	Node("int", 1),
	Node("dict", Node(
		"nested_dict", [
			Node(
				"str", "str"
			),
			Node(
				"nested_nested_dict",
				Node(
					"int", 2
				)
			)
		]
	)),
	Node("list", [
		Node(
			"list_nested", [
				Node("list_nested_nested", Node("int", 1))
			]
		),
		Node(
			"int", 4
		)
	])
])


def deserialize_object(object_to_deserialize):
	deserialized_object_dict = {}

	if isinstance(object_to_deserialize.value, Node):
		deserialized_object_dict[object_to_deserialize.key] = deserialize_object(object_to_deserialize.value)

	elif isinstance(object_to_deserialize.value, (set, list, tuple)):
		object_to_deserialize_values = []

		for obj in object_to_deserialize.value:
			if isinstance(obj.value, Node) or isinstance(obj.value, (set, list, tuple)):
				object_to_deserialize_values.append(deserialize_object(obj))
			else:
				object_to_deserialize_values.append({obj.key: obj.value})

		deserialized_object_dict[object_to_deserialize.key] = object_to_deserialize_values

	else:
		deserialized_object_dict[object_to_deserialize.key] = object_to_deserialize.value

	return deserialized_object_dict
	
	
print(deserialize_object(example_of_object_to_deserialize))

Див. також

• Рекурсія
• Хвостова рекурсія
• Рекурсивні функції (математичне визначення)
• Операція примітивної рекурсії
• Процедура (програмування)

Джерела

• Енциклопедія кібернетики, Халілов А. І., т. 2, с. 251-252.

Посилання

• IBM developerWorks: Mastering recursive programming [Архівовано 7 листопада 2006 у Wayback Machine.] — (англ.) переваги та недоліки, правила програмування рекурсивних процедур.