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

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

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

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

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

  • обчислення факторіалу 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))

Див. також

Джерела

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.