ZAMYLA : 이해하기 위해서 재귀, 당신은해야 첫 번째 재귀를 이해합니다. 프로그램 설계 수단에 재귀를 갖는 당신은 자기 참조를 가지고 정의. 재귀 데이터 구조들, 예를 들어, 데이터 구조는 그 자신을 포함 그 정의. 그러나 오늘, 우리는 초점을거야 재귀 함수에. 

함수는 입력을 리콜 인수와 같은 값을 반환 자신의 로 표시되는 출력 여기이 그림. 우리는 몸으로 상자를 생각합니다 세트의 함수를 포함하는, 해석 지침 입력과 출력을 제공합니다. 신체의 내부를 자세히 살펴보면 함수 호출을 공개 할 수 다른 기능뿐만 아니라. 이 간단한 기능, foo는, 가지고 그 입력으로 하나의 문자열을 받아 인쇄 얼마나 많은 편지 해당 문자열이 있습니다. 문자열 길이에 대한 함수 나 strlen,, 출력이 있습니다,라고합니다 printf의 호출에 필요합니다. 

자, 어떻게 재귀 함수를 만든다 특별한는 자신을 호출한다는 것입니다. 우리는이 재귀를 나타낼 수 있습니다 이 주황색 화살표로 전화 다시 자체를 반복합니다. 그러나 자신을 다시 실행 만 것 다른 재귀 호출을하고, 서로 다른. 하지만 재귀 함수 무한이 될 수 없습니다. 그들은 어떻게 든 종료해야하거나 이 프로그램은 영원히 실행됩니다. 

그래서 우리는 휴식 할 수있는 방법을 찾을 필요가 재귀 호출의 중. 우리는 기본 경우이를 호출합니다. 베이스 케이스 조건이 충족 될 때, 함수 않고 반환 다른 재귀 호출. 무효 함수에게, 안녕,이 기능을 그 입력으로 INT 해당됩니다. 기본 케이스가 먼저 온다. N이 0보다 작은 경우, 인쇄 안녕과 경우 다른 모든 경우 반환 기능은 하이 인쇄 실행됩니다 재귀 호출. 와 기능 안녕 또 다른 전화 감소 입력 값. 

이제, 우리는, 하이 인쇄에도 기능을 종료하지 않습니다 우리까지 반환 형식을 반환 이 경우 무효에. 그래서 매 n 기본 케이스 이외의 경우, 이 기능 안녕 안녕 리턴합니다 N 마이너스 1. 이 기능은하지만 무효이기 때문에, 우리 여기에 명시 적으로 리턴을 입력하지 않습니다. 우리는 단지 기능을 수행합니다. 그래서 하이 호출하면 (3) 하이 인쇄합니다 안녕하세요 (2) (1) 하나의 안녕을 실행하는 실행 하이를 실행하는 (0), 여기서 기본 경우 조건이 충족됩니다. 그래서 하이 (0) 안녕 인쇄하고 돌아갑니다. 

OK. 그래서 지금 우리의 기본을 이해하는 것이 그들이 필요로하는 것을 재귀 함수, 적어도 하나의 기본 케이스뿐만 아니라 재귀 호출의가로 이동하자 더 의미있는 예. 다만 반환하지 않는 한 상관없이 무효가 없습니다. 

의이 요인을 살펴 보자 조작에 가​​장 일반적으로 사용 확률 계산. N의 요인마다의 제품입니다 보다 긍정적 인 정수를 n은 동일. 그래서 계승 다섯은 5 배 4 배 3 회 2 회 1 (120)을 제공한다. 네 가지 요인은 4 배 3 배 2 회 1 (24)을 얻었다. 그리고 동일한 규칙이 적용됩니다 임의의 양의 정수. 

그래서 우리가 어떻게 재귀를 작성할 수 있습니다 계승을 계산 기능 수? 음, 우리는 모두 확인해야합니다 기본 케이스와 재귀 호출. 재귀 호출은 동일합니다 베이스를 제외한 모든 경우에 경우, 이는 우리가해야합니다 것을 의미합니다 우리에게 줄 것이다 패턴을 찾아 우리의 원하는 결과. 

이 예를 들어, 어떻게 5 계승 참조 1 2 3 4를 곱 포함 그리고 바로 그 같은 곱셈 여기 발견 4 팩토리얼의 정의. 그래서 우리는 5 요인이라고 볼 다만 5 배 4 계승. 이제이 패턴이 적용 되는가 4뿐만 아니라 계승? 예. 우리는 4 요인에 포함 된 참조 곱셈 3 회 2 회 1, 3 계승 매우 동일한 정의. 그래서 4 계승 4 배 3과 같다 계승하고, 등등 등등 우리 패턴은 1 요인까지 붙어있는 정의에 의해 1과 동일하다. 

다른 양의가 없습니다 정수는 왼쪽. 그래서 우리의 패턴이 우리의 재귀 호출. N 계승의 n 배와 같다 N의 계승 - 1. 그리고 우리의 기본 케이스? 그건 단지 우리의 정의가 될 수 있습니다 1 계승. 

그래서 지금 우리가 쓰기로 이동할 수 있습니다 함수에 대한 코드입니다. 기본 케이스를 위해, 우리는해야합니다 조건, n은 같음 1, 동일 위치 우리는 1을 반환합니다. 그런 다음 재귀 호출로 이동 우리는 N 번 돌아갑니다 N의 계승 - 1. 

이제이 우리를 테스트 할 수 있습니다. 의이 계승 4 해보자. 우리의 함수 당은 동일한의 4 배 팩토리얼 내지 (3). 요인 (3)과 동일 3 회 계승 (2). 요인 (2) 2 배에 해당합니다 계승 (1), 이는 1을 반환합니다. 요인 (2) 지금 2 회 1, 2를 반환합니다. 요인 (3) 지금 반환 할 수 있습니다 3 회 2,6. 그리고 마지막으로, 계승 (4) 4 회 6, 24을 반환합니다. 

당신은 어떤 어려움이 발생하는 경우 재귀 호출, 그 척 기능이 이미 작동합니다. 내가이 의미하는 것은 당신이해야하는 돌아가려면 재귀 호출을 신뢰 오른쪽 값. 예를 들어, 내가 알고있는 경우에 그 계승 (5) 5 배 같은지 계승 (4), 그 신뢰거야 계승 (4) 나에게 24을 제공 할 것입니다. 당신이 경우, 변수로 생각 것입니다, 당신은 이미 정의 된 경우 등 계승 (4). 그래서 어떤 요인에 (N), 그건 N의 제품과 이전의 계승. 그리고이 이전의 계승 호출하여 얻을 수있다 N의 계승 - 1. 

당신이 구현할 수있는 지금, 만약 참조 재귀 함수를 직접. 터미널을로드, 또는 run.cs50.net, 및 함수 합 쓰기 즉, 정수 n을 받아 반환 모든 연속적인 양의 합 n은 1 내지 정수. 나는 약간의 금액을 서면으로 작성했습니다 당신을 도울 수있는 값을 우리의. 첫째, 파악 기본 케이스 상태. 그런 다음, 합계 봐 (5). 당신은 측면에서 표현 할 수 있습니다 다른 합? 자, 어떤 합계에 대한 (4)? 어떻게 합계를 표현할 수 있습니다 (4) 다른 화의 측면에서? 

당신이 합이되면 (5)과 합계 (4) 다른 액수 등의 측면에서 볼 당신을 식별 할 수있는 경우 합 (N)에 대 한 패턴입니다. 그렇지 않은 경우, 몇 가지 다른 번호를 시도 그들의 합계 간편 다른 숫자의 측면. 이산 패턴을 식별하여 숫자, 당신은 당신의 방법에 잘있어 모든 N의 패턴을 식별. 

재귀는 정말 강력한 도구입니다, 그래서 당연히 그것을 제한되지있어 수학 함수. 재귀는 매우 효율적으로 사용할 수 있습니다 예를 들어 나무를 처리 할 때. 위해 나무에 짧은 체크 아웃 더 철저한 검토,하지만 지금은 에, 그 이진 검색 트리를 불러 특히, 각각의 노드로 구성되어 있습니다 값과 두 개의 노드 포인터. 보통,이은으로 표시됩니다 한 줄을 가리키는 데 부모 노드 왼쪽 자식 노드와 하나 오른쪽 자식 노드에. 이진 검색의 구조 나무는 잘 빌려 준다 재귀 검색 할 수 있습니다. 재귀 호출은 하나의 통과 왼쪽이나 오른쪽 노드,하지만 더 트리 짧은 그. 

당신이에서 작업을 수행 할 말 이진 트리의 모든 단일 노드. 어떻게 그것에 대해 갈 수 있을까요? 글쎄, 당신은 재귀를 작성할 수 연산을 수행하는 기능 부모 노드와 재귀를 만든다 동일한 함수 호출 왼쪽에 전달하고 오른쪽 자식 노드. 예를 들어,이 기능, foo는, 그 주어진 노드의 값을 변경합니다 1 모든 자식. NULL 노드 원인의 기본 케이스 기능을 나타내는 돌아갑니다 모든 노드가 아니라는 것을 그 하위 트리에 남아. 

의 그것을 통해 살펴 보겠습니다. 첫 번째 부모는 13입니다. 우리는이 값을 1로 변경 한 다음 전화 우리의 왼쪽에있는 기능뿐만 아니라 오른쪽으로. 함수 foo는이, 왼쪽에서 호출 첫 번째 서브 트리, 그래서 왼쪽 노드 1 foo는 재 할당 할 것 해당 노드의 자식에서 호출, 먼저 왼쪽하고 오른쪽, 등 등. 분기에는없는 그들에게 어떤 추가 아이들 때문에 동일한 프로세스 오른쪽 아이들을 위해 계속 전체 트리의 노드가 될 때까지 1에 재 할당. 

당신이 볼 수 있듯이, 당신은 제한되지 않는다 단지 하나의 재귀 호출. 작업을 수행하는 것만큼이나 많은. 당신은 나무를 가지고 어떤 경우 여기서 각 노드는 세 자녀를했다, 왼쪽, 중간, 오른쪽? 어떻게 foo는 편집까요? 음, 간단하게. 그냥 다른 재귀 호출을 추가하고 중간 노드 포인터를 전달합니다. 

재귀는 매우 강력하고하지 않는 것입니다 우아한 물론이지만 될 수 처음에는 어려운 개념 때문에 수 환자와 당신의 시간이 걸립니다. 기본 케이스와 함께 시작합니다. 그것은 일반적으로 식별하는 가장 쉬운 방법이다, 다음은 작동 할 수있다 거꾸로 거기에서. 당신은 당신이 도달 할 필요가 알고 당신의 기본 케이스, 그래서 힘 당신에게 몇 가지 힌트를 제공합니다. 하나의 특별한 경우를 표현하려고 다른 경우의 조건, 또는 서브 세트에. 

이 짧은 시청 해 주​​셔서 감사합니다. 적어도, 지금 당신은 할 수 있습니다 이 같은 농담을 이해합니다. 내 이름은 Zamyla이며,이 CS50입니다. 

안녕하세요,이 기능을 가지고, 소요 무효 기능 INT, N, 입력으로. 기본 케이스가 먼저 온다. N이 0보다 작은 경우, 인쇄 경우 "안녕"하고 돌아갑니다.