как определить вывод сложной рекурсивной функции вручную

Вот рассматриваемый рекурсивный код:

def trace(a, b):
    if (a > b):
        return -1
    elif (a == b):
        print (a * a)
        return a * a
    else:
        m = (a + b) / 2
        return trace (a, m) + trace (m + 1, b)

x=trace(1,4)

хотя я не уверен, что эта функция должна делать, мы должны найти вывод x=trace(1,4) вместе со значением x вручную (это означает, что мы не можем использовать простоя, чтобы помочь нам).

Через некоторое время я определил, что функция напечатает 1 и 12,25, что и будет выводом при присвоении x значению trace(1,4).

Однако я не знаю, как определить, каким будет значение X. Хотя ответ равен -91,75, я не имею ни малейшего представления о том, как он был получен (хотя я знаю, как, потребовалась бы целая вечность, чтобы придумать этот ответ, и я не уверен, как мы можем быстро придумать ответ). решение за короткий период времени, например, при написании экзамена).

Заранее спасибо за помощь!


python-3.x python recursion tail-recursion
person rexorsist    schedule 12.12.2017    source источник
comment
8-я строка должна быть m = (a + b) // 2. Таким образом, это будет работать одинаково в Python2 и Python3.   -  person Eric Duminil    schedule 12.12.2017
comment
@EricDuminil: Юпп, это определенно вопрос о Python 2, но его можно заставить работать в Python 3, исправив его по-своему.   -  person Sherlock70    schedule 12.12.2017

Ответы (2)


arrow_upward
2
arrow_downward

Во-первых, я обманул. Вот несколько советов, связанных с моей грудью: эта функция определенно не предназначена для Python 3! Причина в операторе /. В Python 2 это приводило к целым числам, в Python3 — к числам с плавающей запятой. Итак, учитывая это предварительное условие, вот мое решение:

Функция не сложная. Тип данных каждой из ваших переменных — целочисленный! m всегда будет целым числом. x равно 30. Уровень рекурсии равен трем, что соответствует семи вызовам вашей функции (включая первый). И вот как вы поступаете с такими вещами: возьмите бумагу и ручку и просто записывайте каждый шаг.

  1. Ввод: a = 1 и b = 4, что приводит к другой части вашей функции... пока нет вывода. Здесь m вычисляется как (1+4)/2. В моей книге это 2,5. Но это округляется до 2, потому что у нас есть целые числа. Затем рекурсия начинается с двух вызовов (1,2) и (3,4)
  2. Давайте посмотрим на (1,2): a=1 и b=2. Опять никаких выходных данных, и мы переходим прямо к другой части: m вычисляется как 3/2, что составляет хорошие 1,5, округленные до 1. Снова два вызова функции с новыми параметрами (1,1) и (2, 2). Обратите внимание, что оба вызова теперь будут входить в elif-часть функции, и каждый будет производить вывод и возвращаемое значение. Вы можете заменить (1,1) на 1 и (2,2) на 4. Здесь выполняется рекурсия, и вызов trace(1,2) приводит к 5. Давайте посмотрим на другую ветвь рекурсии.
  3. Входными данными являются a=3 и b=4, что приводит к еще одной паре вызовов со следующими параметрами: (3,3) и (4,4). Думаю, к настоящему времени вы должны освоиться. Самое интересное состоит в том, чтобы сложить все возвращаемые значения в том виде, в котором они были предоставлены.

Что делает функция: она суммирует все квадраты всех целых чисел между a и b.

person Sherlock70    schedule 12.12.2017
comment
Спасибо большое за вашу помощь. Мне никогда не приходило в голову, что этот код может быть предназначен для Python 2. Это вполне может быть опечаткой моего профессора, поскольку он был предназначен для Python 3, что раздражает, поскольку я потратил много часов, пытаясь определить результат с ручкой и бумагой. . Использование целых чисел имеет гораздо больше смысла и делает это намного проще. Спасибо еще раз! - person rexorsist; 12.12.2017
comment
@rexorsist: Оооо, что вы думаете? Приемлем ли ответ или чего-то не хватает? - person Sherlock70; 13.12.2017
comment
Чувак, я ненавижу, когда это происходит. Я приложил немало усилий к своему ответу, и он просто не будет принят, потому что новичку, похоже, все равно. - person Sherlock70; 19.01.2018

arrow_upward
1
arrow_downward

взгляните на эти строки:

m = (a + b) / 2
return trace(a, m) + ...

эти строки выполняются только в том случае, если b больше a. Это означает, что m всегда будет больше, чем a, и первый рекурсивный вызов функции имеет точно такую ​​же проблему. Со значениями a = 1 и b > a m сходится к 1. Теоретически рекурсия никогда не заканчивается, поскольку m никогда не будет 1.0 или меньше. Однако точность с плавающей запятой ограничена, поэтому существует точка (после многих рекурсивных вызовов), когда процессор не может m отличаться от 1.0. В этот момент elif (a == b): становится истинным и останавливает рекурсию. Это не объясняет, почему результат равен -91.75, но показывает, почему почти невозможно отобразить все рекурсивные вызовы на диаграмме, в дереве или в чем-то еще. Я надеюсь, что это помогает.

person Aemyl    schedule 12.12.2017
comment
Да, я смог определить, что ближе к концу, когда он запрашивает возврат trace(a,m)+trace(m+1,b), этот trace(a,m) будет сходиться к print(1), а trace (m+1,b) будет сходиться к print(12), что согласуется с результатом в IDLE. Я предполагаю, что -91,75 исходит из того, сколько рекурсивных вызовов требуется, чтобы m стало равным 1,0 в соответствии с IDLE. Я просто не знаю, как кто-то определил бы это с ручкой и бумагой. - person rexorsist; 12.12.2017