Другой кодер запутался в рекурсии

Предположим, я хотел сложить два числа, но могу увеличивать и уменьшать только на 1. Я могу решить эту проблему несколькими способами, в том числе с помощью рекурсии. Когда я добавляю m и n, я могу использовать следующее определение Python:

def slowAdd(m, n):
    if n == 0:
       return m
    else:
       return 1 + slowAdd(m, n-1)

Меня это действительно сбивает с толку. Может кто-нибудь объяснить, как работает последний обратный звонок? Как Python интерпретирует значение определенной функции при добавлении ее к 1?


python recursion return algorithm
person oliver    schedule 30.01.2017    source источник
comment
Это не значение определенной функции, это возвращаемое значение вызова функции. Вам это поможет?   -  person Fred Larson    schedule 31.01.2017
comment
Он добавляет то, что возвращает slowAdd(m, n-1). Итак, если бы у вас было def f(n): return 8 - n и 1 + f(1), вы получили бы 8.   -  person juanpa.arrivillaga    schedule 31.01.2017
comment
Прочтите статью в Википедии о рекурсии.   -  person Barmar    schedule 31.01.2017
comment
Мне обычно не нужно использовать функцию цикла для этого типа эффекта?   -  person oliver    schedule 31.01.2017
comment
@Oliver Recursion - это тип цикла.   -  person Barmar    schedule 31.01.2017
comment
Но я не определил это как таковое ...   -  person oliver    schedule 31.01.2017
comment
Рекурсия: см. Рекурсия   -  person Fred Larson    schedule 31.01.2017
comment
@Oliver, вы не определили что как таковое?   -  person juanpa.arrivillaga    schedule 31.01.2017
comment
@ juanpa.arrivillaga цикл. Он не написал ничего столь же явного, как recursion with slowAdd(), как он написал бы с for или while циклами. Думаю, он отвечал на @Barmar.   -  person spicypumpkin    schedule 31.01.2017

Ответы (5)


arrow_upward
5
arrow_downward

Что ж, давайте посмотрим на суперпростую функцию.

def super_simple_function():
  return 0

Что произойдет, когда я сделаю x = super_simple_function()?

>>> x = super_simple_function()
>>> x
0

Это потому, что значение функции return равно нулю. Итак, есть объект-функция, который при вызове дает (возвращает) вам значение.

Давайте посмотрим на вашу рекурсивную функцию построчно. Представьте, что мы передали 2 и 3 в качестве аргументов, например: slowAdd(2, 3).

Строка 1: def slowAdd(m, n)
Это означает, что первый аргумент равен m, а второй - n. Следовательно, в нашем случае m = 2 и n = 3.

Строка 2: if n == 0
Это условие, которое срабатывает, когда n equals to 0. Что ж, прямо сейчас n = 3, поэтому это условие игнорируется.

Строка 3: return m
Поскольку n не равно 0, эта строка пока игнорируется; мы вернемся к этому.

Строки 4 и 5: else: return 1 + slowAdd(m, n-1)
Здесь происходят три вещи.

  1. Получаем возвращаемое значение slowAdd(m, n-1).
  2. Добавляем 1 к возвращаемому значению
  3. Возвращаем сумму из №2.

Эта функция называется рекурсивной из-за №1. Как вы понимаете, эта функция будет вызывать сама себя до n == 0, после чего она вернет m вместо 1 + slowAdd(m, n-1). И поскольку мы уменьшаем n на 1 в каждой рекурсии, мы точно знаем, что n в конечном итоге будет равно 0.

В основном это то, что делает функция, когда мы передаем (2, 3) в качестве аргументов:

1st recursion: return 1 + slowAdd(2, 2)
2nd recursion: return 1 + slowAdd(2, 1)
3rd recursion: return 1 + slowAdd(2,0)
4th recursion: return 2            # n is finally 0!

Что в сумме составляет 2 + 1 + 1 + 1 = 5.

person spicypumpkin    schedule 30.01.2017

arrow_upward
4
arrow_downward

Подумайте об этом как о замене «slowAdd (m, n-1)» на правильное возвращаемое выражение (либо «m», если n = 0, либо «1 + slowAdd (m, n-1)»).

Пример:

slowAdd(5,3)
1 + slowAdd(5, 3-1)
1 + (1 + slowAdd(5, 2-1))
1 + (1 + (1 + slowAdd(5, 1-1)))
1 + (1 + (1 + 5))) // n=0
person jlau    schedule 30.01.2017

arrow_upward
1
arrow_downward

Во время обратного вызова для n! = 0 функция снова вызывает себя, добавляя 1 к n-1-му значению. Я бы лучше объяснил это иллюстрацией. Ниже показано, что происходит с вашей вызванной функцией: (slowAdd (1,3) :)

slowAdd(1,3)
 returns 1+slowAdd(1,2)
           returns 1+slowAdd(1,1)
                     returns 1+slowAdd(1,0)
                               returns 0

Итак, что происходит:

 1+3
=1+(1+2)
=1+(1+(1+1))
=1+(1+(1+(1+0)))
person iamnotgoogle    schedule 30.01.2017

arrow_upward
1
arrow_downward

Вы можете добавить оператор печати внутри цикла и видеть, что происходит, также строку if n == 0: можно записать как if not n:

def slowAdd(m, n):
    if not n: return m
    else:
        print('1 + ({}, {})'.format(m, n))
        return 1 + slowAdd(m, n-1)


print(slowAdd(5,5))
1 + (5, 5)
1 + (5, 4)
1 + (5, 3)
1 + (5, 2)
1 + (5, 1)
10
person Simeon Aleksov    schedule 30.01.2017

arrow_upward
1
arrow_downward

когда мы выполняем программу, мы называем стек выполнения

когда функция (A) вызывает другую функцию (B). программа сохраняет контекст функции A в стеке выполнения, чтобы она могла продолжить выполнение функции (A) после завершения функции (B).

контекст - это все локальные переменные функции и оставшиеся инструкции.

Предположим, что мы вызываем функцию, подобную этой slowAdd (1,9), перед вызовом slowAdd (1,9) программа сохранит контекст, поэтому она сохранит текущее значение n = 1 и текущее значение m = 9 и последняя инструкция, которая равна 1 + slowAdd (0,9), затем она вызовет slowAdd (0,9). slowAdd (0,9) вернет 9, и программа вернется к первому вызову функции. он восстановит контекст и заменит вызов возвращаемым значением. 1 + slowAdd (0,9) будет 1 + 9

person Mohamed Amine Ouali    schedule 30.01.2017