Рекурсия в математике

[likusta]

Можете привести несложный пример, где для решения математического задания требуется использование рекурсии или это не удобно, кроме программирования.

[Профессор Снэйп]

Ханойские башни

[likusta]

Действительно, но на много удобней решение через программу(В Pascal только процедура), человек пока проводит эти вычисления не очень быстро, рекурсия упрощает задачу, переводя ее в некое дерево, и решение идет от листьев к корню(если в задаче "Ханойские башни" взять, предположим, 1000 слоев, сомнительно, что решение будет быстрым) . Поэтому перефразирую свой вопрос, сталкивались ли вы с тем, что для доказательства гипотезы, была необходимость использовать рекурсию. Этот подход к решению помогает? Или можно обойтись без рекурсии в математике?:

[ИСН]

Подумайте про теорему Гудстейна или ещё какое-нибудь отрубание голов у гидры. Но вообще-то это другое. Рекурсия как таковая - это понятие из программирования, а не из математики.

[Профессор Снэйп]

likusta в сообщении #257620 писал(а):

...сталкивались ли вы с тем, что для доказательства гипотезы, была необходимость использовать рекурсию.

Каждое доказательство, использующее принцип математической индукции, сталкивается с этим

[Maslov]

ИСН в сообщении #257625 писал(а):

Рекурсия как таковая - это понятие из программирования, а не из математики.

А как же теория вычислимости?

[Профессор Снэйп]

"Программирование" и "чистая математика" не так уж далеки друг от друга, как Вам кажется. Например, задача о существовании решения для ханойской башни произвольной высоты относится к области чистой математики. Или, если для Вас ханойские башни так прочно связаны с программированием, подумайте над вычислением интеграла

$$ \int \sin^n x \, dx $$

для произвольного натурального $n$. Это что: программирование или математика?

[Stude]

действительно существуют интегралы, где решение выражается через предыдущие решения

[likusta]

Профессор Снэйп в сообщении #257634 писал(а):

"Программирование" и "чистая математика" не так уж далеки друг от друга, как Вам кажется.

Мне так не кажется.Я хотел узнать какая эффективность у рекурсии и как ее применяют в математике и все. А решения задач могут быть различными, вопрос один: рационально ли это?

[Профессор Снэйп]

likusta в сообщении #257642 писал(а):

А решения задач могут быть различными, вопрос один рационально ли это?

Изначально вопрос был другой!

likusta в сообщении #257598 писал(а):

Можете привести несложный пример, где для решения математического задания требуется использование рекурсии...

$$ \int \sin^n x \, dx $$

Годится?

[likusta]

Профессор Снэйп в сообщении #257644 писал(а):

likusta в сообщении #257642 писал(а):

А решения задач могут быть различными, вопрос один рационально ли это?

Изначально вопрос был другой!

likusta в сообщении #257598 писал(а):

Можете привести несложный пример, где для решения математического задания требуется использование рекурсии...

$$ \int \sin^n x \, dx $$

Годится?

Да, большое спасибо.
Следующий раз буду точнее с вопросом. Не получилось сразу сформулировать.

[wall-e]

Ну если брать банальный пример, то это опредедение факториала числа. Если n=1, то n!=1. если n>1 то n!=n*(n-1)!. и так далее.

[e2e4]

Вот тут недавно обсуждалось совершенно то же самое.
Кстати, Maslov, насчет аргументов насчет того, что рекурсия в 100% случаев теоретически может быть сведена к итерации, помню, и ищу на досуге. Как будет что-то дельное, отпишусь.

[Профессор Снэйп]

Кстати, деревья --- одно из основных математических понятий. Теоремы про них доказываются рекурсией (i.e. индукцией) по высоте дерева (ординальному типу дерева для бесконечных деревьев)...

-- Вт ноя 03, 2009 21:57:23 --

Судья: подсудимый, за что вы убили старушку?

Обвиняемый: ну, понимаете, мы ехали в автобусе. К ней подошёл кондуктор, попросил денег за проезд. Она открыла сумочку, достала кошёлку, закрыла сумочку, открыла кошёлку, достала из неё кошелёк, закрыла кошёлку, открыла сумочку, положила кошёлку, закрыла сумочку, открыла кошелёк, достала деньги, закрыла кошелёк, открыла сумочку, достала кошёлку, закрыла сумочку, открыла кошёлку, положила кошелёк, закрыла кошёлку, открыла сумочку, положила кошёлку, закрыла сумочку. Дала кондуктору деньги, он дал ей билет и сдачу. Она открыла сумочку, достала кошёлку...

-- Вт ноя 03, 2009 22:17:18 --

Цитата:

РАСПОРЯЖЕНИЕ ПРЕЗИДЕНТА УКРАИНЫ № 161/2009-рп

Об отмене Распоряжения Президента Украины от 6 марта 2009 года № 38

Отменить Распоряжение Президента Украины от 6 марта 2009 года № 38 «Об отмене распоряжения Президента Украины от 13 декабря 2007 года № 292».

Президент Украины Виктор ЮЩЕНКО

31 июля 2009 года

[Maslov]

e2e4 в сообщении #257995 писал(а):

Кстати, Maslov, насчет аргументов насчет того, что рекурсия в 100% случаев теоретически может быть сведена к итерации, помню, и ищу на досуге. Как будет что-то дельное, отпишусь.

Хорошо.
Кстати, особых сомнений в том, что рекурсия может быть сведена к итерации, не было. Были сомнения в существовании доказательства того, что любой рекурсивный алгоритм может быть сведен к более эффективному итеративному.