[음악 재생] 

DOUG 로이드 : 당신은 아마 생각 코드는 작업을 수행하는 데 사용된다. 당신은 그것을 쓰는. 그것은 무언가를. 즉, 꽤 많이 있습니다. 

당신은 그것을 컴파일합니다. 당신은 프로그램을 실행합니다. 당신은 갈 수 있어요. 

하지만 믿거 나 말거나, 경우 만약 오랜 시간 동안 코딩 당신은 실제로보고 올 수도 아름다운 무언가로 코드. 이 문제의 해결 매우 흥미로운 방법, 나 정말 뭔가있다 보이는 방법에 대한 깔끔한. 당신은 웃음 될 수 있습니다 나, 그러나 그것은 사실입니다. 그리고 재귀 하나의 방법입니다 종류의이 아이디어를 얻을 수 있습니다 아름다운, 우아한 보이는 코드. 이 방법으로 문제를 해결하는 시각화하기 쉽고, 재미있다 그리고 놀라 울 정도로 짧은. 

방법 재귀 작품 재귀 함수이며, 호출하는 함수로 정의된다 자체의 실행의 일환으로. 즉, 조금 이상하게 보일 수 있습니다 우리는 조금 볼 수 있습니다 이 순간에 작동하는 방법에 대한. 그러나 다시,이 재귀 절차는 그래서 우아한 될 것 그들이려고하고 있기 때문에 않고이 문제를 해결하기 위해서 모든 다른 기능을 갖는 또는 롱 루프. 이러한 순환 것을 볼 수 있습니다 절차는 매우 짧은 보는 것입니다. 그리고 그들은 정말 만들려고하고있다 코드가 훨씬 더 예쁘다. 

나는 당신에게 예를 들어주지 이런 방식을 볼 수 있습니다 재귀 프로 시저를 정의 할 수 있습니다. 당신이 잘 알고 있다면 몇 년 전 수학 클래스 뭔가라고 통상 팩토리얼 함수 느낌표로 표시되는 모든 양의 정수에 대해 정의된다. 그리고 방법이 N 계승 계산한다 당신은 모두를 곱하면된다 보다 숫자 이하 거나 같은 N together--하기 모든 정수보다 적은 또는 함께 N과 동일. 

그래서 5 계승은 5 배 4 회 3 회 2 회 1. 그리고 4 계승 4 배 3 회 2 회 1 등. 당신은 아이디어를 얻을. 

프로그래머로서, 우리는하지 않습니다 N, 느낌표를 사용합니다. 그래서 우리는 계승을 정의합니다 N의 사실과 같은 기능. 그리고 우리는 만들 계승을 사용합니다 문제에 대한 재귀 솔루션입니다. 그리고 난 당신이 찾을 수있는 생각 그것은 많은 시각적 있다고 반복보다 매력 이 버전, 어떤 우리는 또한 잠시 살펴 보겠습니다. 

그래서 여기의 커플 facts-- 말장난 intended-- 대한 factorial-- 계승 기능. 내가 말한대로 1의 계승은 1입니다. 2의 계승은 2 회 1입니다. 3의 계승은 3 2 배 등등 시간 1합니다. 우리는 이미 4와 5에 대해 이야기했다. 

그러나이보고,이 사실이 아니다? 2의 팩토리얼되지 않은 단지 2 회 1의 계승? 내 말은, 1의 계승은 1입니다. 그런데 왜 우리는 그냥 말할 수 없다, 2의 계승은 2 회 1이기 때문에, 정말 단 2 번이다 1의 계승? 

그리고, 그 생각을 확장 3의 계승되지 않습니다 다만 3 회 2의 계승? 그리고 4의 계승은 4 배 그래서 3,의 계승? 사실, 계승 임의의 숫자의 단지 수 종류 우리 경우 표현 영원히이를 실시하고 있습니다. 우리는 종류의 일반화 할 수 있습니다 계승 문제 그것의로 n 배 N 마이너스 1의 계승. 그것은의 n 번 제품의 모든 숫자 나보다. 

이 생각이 문제의 일반화, 우리가 반복적으로 할 수 있습니다 팩토리얼 함수를 정의. 당신은 함수를 정의 할 때 재귀 적있다 그것의 일부가 될 필요가 두 가지. 당신은 뭔가를 호출이 필요합니다 기본 케이스,있는, 당신이 그것을 실행할 때, 재귀 프로세스를 중지합니다. 

그렇지 않으면, 함수는 호출 itself-- 당신이 imagine-- 수로 영원히 갈 수 있습니다. 함수는 함수를 호출 함수 호출을 호출 기능 함수를 호출한다. 만약이 방법이 없다면 , 프로그램을 중지합니다 효과적으로 붙어됩니다 무한 루프에서. 그것은, 결국 충돌합니다 이 메모리가 부족할 것이기 때문에. 하지만 그 점 옆에 있습니다. 

우리는 막을 다른 방법이 필요합니다 우리의 프로그램 충돌 이외의 것들 충돌하는 프로그램이기 때문에 아마 아름다운 또는 우아한 없습니다. 그래서 우리는이 기본 케이스 전화. 이것은 간단한 해결책 정지 문제 발생의 순환 과정. 그래서의 한 부분이다 재귀 함수. 

두 번째 부분은 재귀 경우이다. 그리고 이것은 어디 재귀입니다 실제로 일어날 것이다. 이것은 어디 기능 자체를 호출합니다. 

그것은 정확히에서 자신을 호출하지 않습니다 같은 방법은 호출했다. 그것은 약간의 변화를 알 수있을 것입니다 즉, 그것의 문제를 만든다 조그마한 조금 작은 해결하기 위해 노력. 그러나 일반적으로 벅 전달 용액의 부피를 해결 선 아래로 다른 통화에. 

이러한 외모의 어떤 여기에 기본 케이스 같은? 어느 등이 모습 중 하나 문제에 대한 간단한 해결책? 우리는 계승의 무리를 가지고, 우리는 계속할 수 그래서 on-- 6, 7, 8, 9, 10,가는. 

그러나 같은 이러한 모습 중 하나 좋은 경우는 기본 경우가 있습니다. 그것은 매우 간단한 솔루션입니다. 우리는 특별한 아무것도 할 필요가 없습니다. 

1의 계승은 1입니다. 우리는 어떤 작업을 수행 할 필요가 없습니다 곱셈 전혀. 우리는 거 야 것 같다 시도하고 이러한 문제점을 해결하기 위해, 우리는을 중지해야 어딘가에 재귀, 우리는 아마 중지하려면 그것은 우리가 1에 도착하면. 우리는 그 전에 중지하고 싶지 않아요. 

우리가 정의하는 경우에 따라서 우리의 계승 기능, 여기에 해골에 대한이야 우리는 그렇게 할 수있는 방법에 대해 설명합니다. 우리는이 두 things--를 연결해야합니다 베이스 케이스와 재귀 케이스. 기본 케이스는 무엇입니까? N이 1 인 경우, 반환 1-- 그건 정말 간단한 문제가 해결합니다. 

1의 계승은 1입니다. 그것은하지 1 회 아무것도입니다. 그것은 단지 1입니다. 그것은 매우 쉬운 사실이다. 그리고 그것은 우리의 기본 케이스가 될 수 있습니다. 우리는이에 1을 전달받을 경우 기능, 우리는 단지 1을 반환합니다. 

재귀은 무엇인가 경우 아마 같이? 다른 모든 번호 1 외에, 패턴은 무엇인가? 글쎄, 우리가 복용하는 경우 N의 계승, 그것의 n 배의 N 팩토리얼 -1. 

우리가 3의 계승을 복용하는 경우, 그것은, 3 마이너스 1의 3 배 계승의 2. 그리고 우리는 아니에요 그렇다면 그렇지 않으면 1을보고 리턴 n 배 N 마이너스 1의 계승. 그것은 매우 간단합니다. 

그리고 약간 데의 이익을 위해 깨끗하고 코드를 더 우아하고, 알고 우리는 한 줄의 루프가있는 경우 또는 단일 회선 조건 분기, 우리는 모두 제거 할 수있다 주변 중괄호. 그래서 우리는이를 통합 할 수 있습니다. 이 똑같은 갖는다 이 같은 기능을 제공합니다. 

난 그냥 곱슬 멀리 데려 갈거야 하나의 라인이 있기 때문에, 중괄호 그 조건 분기의 내부. 그래서 이들은 동일하게 동작합니다. N이 1이면 1을 반환한다. 그렇지 N 번 리턴 N 마이너스 1의 계승. 그래서 우리는 작은 문제를 만들고있어. n은 5로 밖으로 시작하면, 우리는 갈거야 4의 5 배 계승을 반환합니다. 그리고 우리는 우리가 이야기 할 때 분에 볼 수 있습니다 또 다른 영상 통화 stack--에 대한 여기서 우리가 이야기 우리가 배울 stack-- 전화 정확히이 프로세스가 작동하는 이유에 대해. 

그러나 5의 동안 계승 말한다 5 회 계승 4의 반환, 4 잘 확인을 말할 것입니다, 반환 4 회 3의 계승. 당신이 볼 수 있듯이, 우리는있어 종류의 1에 접근. 우리는 가까워지고있어와 그 기본 케이스에 가까운. 

그리고 우리가 기본 케이스를 공격하면, 이전의 모든 기능 그들이 찾고 있던 답이있다. 2의 요인은 수익을 말하고 있었다 2 회 1의 계승. 음, 1을 반환 1 계승. 계승에 대한 그래서 전화 (2), 2 회 1을 반환 할 수 있습니다 과의 계승에 그 등을 제공 그 결과를 기다리고있다 3. 

그리고 그것을 계산할 수 있습니다 그 결과, 3 회 2, 6이고 4의 계승에 다시 제공합니다. 그리고 다시, 우리는이 호출 스택에 비디오 이것은 조금 설명된다 내가 지금 무슨 말인지보다. 하지만이 그 것이다. 이 혼자가의 해결책 숫자의 계승을 계산. 

그것은 코드의 네 줄입니다. 그건 바로, 정말 멋진입니까? 그것은 섹시한 가지입니다. 

그래서 일반적으로는 아니지만 항상 재귀 함수 에서 루프를 대체 할 비 재귀 함수. 그래서 여기, 나란히는 반복이다 계승 기능의 버전. 이러한 계산의 두 정확히 같은 일. 

그들은 모두 N의 계승을 계산한다. 왼쪽 버전 그것을 할 수있는 재귀를 사용합니다. 오른쪽에있는 버전 그것을 할 수 반복을 사용합니다. 

그리고 통지, 우리는 선언해야 정수 제품 변수입니다. 그리고 우리 루프. 그래서 긴 N으로 우리는, 0보다 큰 N으로 해당 제품을 곱 유지 때까지 N을 감소시키는 우리는 제품을 계산한다. 그래서이 두 가지 기능, 다시, 정확히 같은 일을. 그러나 그들은 그것을하지 않는다 똑같은 방식. 

지금, 그것은 가능하다 하나 이상의 기반을 가지고 케이스 또는 둘 이상의 재귀 경우, 따라 무슨 함수는 무엇을 노력하고있다. 당신은 반드시 단지에 한정되지 않는다 단일 염기 경우 또는 단일 재귀 경우. 뭔가 그래서 예 여러베이스의 경우와 수 있습니다이 항아리 피보나치 수열. 

당신은 기억 할 수 있습니다 초등학교 시절 피보나치 시퀀스가​​ 정의되어 있는지 이 항아리처럼 첫 번째 요소는 0입니다. 두 번째 요소는 1입니다. 이들 모두는 정의된다. 

그런 다음 다른 모든 요소는 정의 n은 마이너스 1 및 n 마이너스 2의 합으로. 세 번째 요소 그래서 0 더하기 1이 1 인 것이다. 그리고 네 번째 요소 두 번째 요소, 1 것, 플러스 세 번째 요소, 1. 그리고는 2 일 것이다. 등등 등등. 

이 경우, 우리는 2 개의 기지국의 경우가있다. N이 1이면 0을 반환한다. N이 2 인 경우, 1을 반환한다. 그렇지 않으면, N의 피보나치를 반환 마이너스 1 플러스 N 마이너스 2의 피보나치. 

그래서 여러 기본 케이스를합니다. 무엇 여러 재귀의 경우는 어떻습니까? 음, 뭔가있다 Collat​​z 추측했다. 나는 말을하지 않을거야 당신은 그게 뭔지 알고 실제로 우리의 최종 왜냐하면 이 특정 비디오에 대한 문제. 그리고 그것은 우리의 운동이다 함께 작업 할. 

그래서 여기에 무슨 콜라 츠 추측 is-- 그것은 모든 양의 정수에 적용됩니다. 그리고 그것이 있다고 추측 항상 가능한 것은 다시 얻을 수 1 다음 단계를 수행합니다. n이 1 인 경우, 정지. n이 1 인 경우 우리는 1로 다시 가지고있다. 

그렇지 않으면,이 통과 과정을 다시 N 2로 나눈. 1로 돌아갈 수 있다면 참조하십시오. n이 홀수 인 경우 그렇지 않으면, 통과 다시 3N 플러스 1에이 과정을, 3 회 N 플러스 1. 그래서 여기에 우리는 단일 염기 경우가 있습니다. N이 1이면 정지. 우리는 더 이상 재귀를 수행하지 않을. 

그러나 우리는 두 재귀 경우가 있습니다. n은 짝수 경우에, 우리는 하나의 순환을 경우는, n은 2로 나눈 전화입니다. n이 홀수이면, 우리는 다른 작업을 수행 3 회 N 플러스 1 재귀 경우. 

그리고이 비디오의 목표는 두 번째를 취할 비디오를 일시 중지하려면 시도이 쓰기 재귀 함수 Collat​​z 어디, n 값에 전달하고 그것은 얼마나 많은 단계를 계산 당신이 N에서 시작하는 경우 (1)에 도착하는 데 걸리는 당신은 위의 해당 단계를 따르십시오. n이 1 인 경우에는 0 단계 걸린다. 그렇지 않으면 것 그러나 한 단계 플러스을 이 중 N 취 많은 단계 (2)에 의해 N 분할은 짝수 또는 3N 플러스 1이면 N이 홀수 인 경우. 

지금, 나는 여기에 화면에 넣었습니다 당신을 위해 테스트 몇 가지, 당신을위한 테스트 케이스의 부부, 볼 이러한 다양한 Collat​​z 번호는 무엇인지, 또한 그림 단계의 그래서 당신이 할 수있는를 통과해야 종류의 행동이 과정을 참조하십시오. n이 동일한 경우는 그래서 1, N의 Collat​​z은 0입니다. 당신은 할 필요가 없습니다 아무것도 1로 돌아 가야합니다. 당신은 이미입니다. 

n이 2 인 경우에는 소요 한 단계 1로 얻을 수 있습니다. 당신은 2로 시작합니다. 그런데,도 2는 1과 동일하지 않다. 그래서 한 걸음이 될 것 플러스 그러나 많은 단계를 에 소요 N 2로 나눈. 

2로 나눈 2는 1 개입니다. 그래서 그러나 한 단계 플러스 소요 많은 단계는 1합니다. 1 제로 조치를 취하고 있습니다. 

당신이 볼 수있는 3를 들어, 거기에 꽤 몇 가지 단계가있었습니다. 당신은 3에서 이동합니다. 그리고 당신은으로 이동 10, 5, 16, 8, 4, 2, 1. 그것은 1로 돌아 가야 일곱 단계를 수행합니다. 당신이 볼 수 있듯이, 거기에 여기에 몇 가지 다른 테스트 케이스 프로그램을 테스트합니다. 그래서 다시, 비디오를 일시 중지합니다. 그리고 이제 다시 뛰어 갈거야 실제 프로세스가 여기에 무엇을, 이 추측은 무엇인지. 

당신이 알아낼 수 있는지 N의 Collat​​z을 정의하는 방법 그것이 얼마나 많은 계산 정도로 그것은 1에 도착하는 데 걸리는 단계를 반복합니다. 그래서 바라건대, 당신은 비디오를 일시 중지 그리고 당신은 나를 기다리고되지 않습니다 여기에 당신에게 대답을 줄 수 있습니다. 그러나 당신이 경우에, 잘, 여기에 대한 대답은 어쨌든입니다. 

그래서 여기에 가능한 정의입니다 Collat​​z 기능. N 인 경우, 우리는베이스 case-- 1과 동일, 우리는 0을 반환합니다. 그것은 어떤을지지 않습니다 단계 1로 돌아 가야합니다. 

그렇지 않으면, 우리는 두 재귀 cases--이 짝수 하나 홀수 하나. 심지어 숫자를 테스트하는 방법 n 개의 모드 (2)는 0에 해당하는지 확인하는 것입니다. 이것은, 다시, 기본적 질문을, 당신은 무엇 모드 is--을 불러주는 경우 나 (2)에 의한 분할 N 더 나머지가 없다? 즉, 짝수 것이다. 

그래서 n 개의 모드 2는 0이 동일한 경우 이 테스트는 짝수이다. 그렇다면, 내가 1을 반환하려면, 이 확실히 때문에 한 단계 플러스의 Collat​​z을 복용 어떤 숫자 나의 절반입니다. 그렇지 않으면, 나는 1을 반환하려면 플러스 Collat​​z의 3 배 N 플러스 1. 즉, 다른이었다 재귀 단계가 우리 를 계산하기 위해 취할 수 단계의 수를 Collat​​z-- 그것은 돌아 가야한다 1로 번호가 부여. 그래서 희망이 예 당신에게 조금 준 재귀 절차의 맛. 바라건대, 당신은 코드가 생각 조금 더하면 아름다운 구현 우아한, 재귀 방법. 도없는 경우에, 재귀가 그럼에도 불구하고 정말 강력한 도구입니다. 그리고 그것은 확실히 뭔가 주위에 당신의 머리를 얻기 위해, 당신은 만들 수있을 것이기 때문에 재귀를 사용하여 정말 멋진 프로그램 그 그렇지 않으면 쓸 복잡 할 수 있습니다 당신은 루프 반복을 사용하는 경우. 나는 더그 로이드입니다. 이 CS50입니다.