누군가이 함수의 재귀 부분이 어떻게 작동하는지 보여 줄 수 있습니까?

Question

필자는 재귀 함수의 예를 들었고 이해하는데 도움이 필요합니다.

def func(x,y): 
    if y == 0: 
     return 0 
    else: 
     return x + func(x,y-1) 

:

나는 재귀 함수가), 나) 인수를 변경하고 기본 케이스쪽으로 이동하고 C)이 코드는 다음과 같습니다

자체를 호출해야합니다 기본 케이스가 있어야합니다 것을 알고있다

저는 func (x, y-1)를 이해하는 데 어려움을 겪고 있습니다. 함수가 x와 y의 곱을 반환한다는 것을 알고 있지만 함수의 재귀 부분이 어떻게 작동하는지 잘 모르겠습니다.

Answer 1

함수는 모든 사용자에게 전화를 걸에 x 그래서 당신이 x의 합이 실제로 함수가 y*x

>>> def func(x,y): 
... if y == 0: 
...  return 0 
... else: 
...  return x + func(x,y-1) 
... 
>>> func(3,4) 
12 
>>> func(3,0) 
0 

이다가 y의 값에 따라 남아 그 다음 0있어 모든 배까지 y의 값을 감소 func(3,4)에 대한 예를 들어, 함수는 반환이 :

3 + func(3,3)= 3+ func(3,2) = 3 + func(3,1) = 3 + func(3,0)= 3+0 

을 우리가을 대체하는 경우s이면 다음과 같을 것입니다. 3+(3+(3+(3+0)))은 12입니다.

Answer 2

이 함수는 x 요소를 y 번 더합니다. 그래서 여기 그것이 작동하는 방법은 다음과 같습니다

는 3와 FUNC, 2를 호출 할 때 다음을 수행의 0 반환 0이 반환하는 조건이 필요한 경우 y는, 0이면

• 확인할 재귀에서.
• 0이 아니면 3 + fun (3, 1)을 추가합니다.이 부분은 스택으로 이동하고 함수를 다시 호출합니다.
• 다시 y 값을 확인하고 3 + func (3, 0)을 수행합니다. 이 부분은 다시 스택으로 이동하여 함수를 다시 호출합니다.
• 이제는 0이므로 3 + fun (3, 0) 스택에서 최상위 요소를 반환하고 fun (3, 0)가 0을 반환하면 3을 반환합니다.
• 우리는 다시 3 + fun (3, 1)을 남긴 pop top 요소입니다. 이전 단계에서 fun (3,1)가 3을 반환 했으므로 fun (3, 1)을 3으로 대체하고 3 + 3 = 6을 반환합니다. - 이제는 스택에 어떤 요소도 없으므로), 6을 리턴하고 호출자에게 리턴합니다. 5,6- (FUNC :

Answer 3

FUNC은 (X는, Y-1)는 단순히 예 6 제 호출 될 것이다 = X & Y-1 예 , 인출 X = 5 새 값으로 다시 FUNC 호출) 그 후, func (5,5) -> func (5,4) -> func (5,3) -> func (5,2) -> func (5,1) func (5,0)

마지막으로 func (5,0)은 호출자에게 0을 반환합니다. & 그것은 & 결국 종료됩니다 한마디로

, 그 함수가 다시 발생 때마다, 그것은 (즉, 두 번째 변수) Y 중 하나 개 적은 값으로 자신을 호출 ... 첫 번째 통화까지 모든 길을 갈 것입니다 y = 0 일 때.

Answer 4

func은 두 개의 인수를 곱하는 함수입니다 (y은 음수가 아닌 정수임). y이 0 인 경우

if y == 0: 
    return 0 

및 x * 0이 x의 값이 0이기 때문에 그것은 분명 사실입니다.그렇지 않으면 x + func(x, y-1)을 반환, 우리는 func(x, y-1)가 x 및 y-1의 제품을 반환한다고 가정하고 있기 때문에, 우리는

x + x*(y-1) = x + x*y - x 
      = x*y 

그렇게 func(x, y)이 실제로 어떤 x 및 음이 아닌 정수 y에 대한 x * y을 반환 확인할 수 있습니다.

내 대학 교수는 "재귀를 신뢰하십시오"라고 말하기 위해 사용합니다. 재귀 호출을 할 때 재귀 호출을 작성할 때 재귀 호출이 "올바른 일"을 반환한다고 가정합니다. 재귀 호출을 원래 호출보다 "더 간단하게"만들면 "그냥 작동합니다".

Answer 5

당신이 말했듯이,이 함수는 스스로를 계속 호출합니다. 이 같은 있었다면 :

def func(x,y): 
    return func(x,y) 

는 끝없이 자신을 부를 것이다 당신에게 결과를 제공하지 않을 것입니다.

그러나 모든 통화에 대해 y를 작게 설정하면 어떤 시점에서 "광기"를 멈출 수 있습니다 (예 : y가 0에 도달하면 그런 다음 y가 1보다 작을 때마다 func (2, 2)는 func (2, 1)을 호출하여 func (2, 0)을 호출합니다. 그러면 y = 0이기 때문에 결국 값을 반환합니다. func (2, 1)은 그 값을 사용하고 그것에 "x"를 추가합니다. 마지막으로 func (2, 2)는 그 반환 값에 x를 더한다. 반환 값은 x 번 y 함수 호출 또는 2 * 2입니다.

Answer 6

또한 다음과 같은 최적화를 수행해야한다는 말을한다 : if y == 0 or x == 0:를, 또는 func(0, 1000)에 대한 호출이 불필요하게 스택 (SICP) 컴퓨터 프로그램의

Answer 7

구조와 해석 값을 둘 것 하나 반복적 인 과정을 설명하는 재귀 적 프로세스는 문제를 해결하기 위해 "그것이 어디서 왔는지 기억해야한다"면서 문제를 해결하는 데 필요한 모든 정보를 "전달"합니다.

구별을 보는 한 가지 방법은 문제의 길이가 어떻게 커지고 다음으로 해결되는지를 추적하는 것입니다.

def func(x,y): 
    if y == 0: 
     return 0 
    else: 
     return x + func(x,y-1) 

func(5,4) 
func(5,4) --> 5 + func(5,3) 
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) 
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + func(5,1) 
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + func(5,1) --> 5 + func(5,0) 
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + func(5,1) --> 5 + func(5,0) --> 0 
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + func(5,1) --> 5 + 0 
func(5,4) --> 5 + func(5,3) --> 5 + func(f,2) -- > 5 + 5 
func(5,4) --> 5 + func(5,3) --> 5 + 5 + 5 
func(5,4) --> 5 + 5 + 5 + 5 
5 + 5 + 5 + 5 
20