[개발자매일영어] Recursion - Cracking Coding Interview

이번에는 Recursion에 대한 내용 입니다.
코딩 인터뷰 문제도 한문제씩 같이 풀어보도록 하겠습니다. 제일 아래에 기출문제가 있습니다. 같이 풀어봐요!

영어 공부는 왕도는 없습니다. 매일 꾸준히 듣고 말하기 연습 하는 것이 가장 중요합니다.

개발자매일영어는 당분간은 Cracking Coding Interview의 저자로 유명한 Gayle Laakmann McDowell저자의 강좌를 지속적으로 공부해보도록 하겠습니다.
전체 분량은 너무 길어서 주요부분 한 두 군데만 1분 이하로 발췌하여 mp3파일로 만들고 있습니다.
즉 한 주제당 1분 이하 분량의 mp3파일이 한 두개씩 제공되겠습니다. 나머지 부분은 리스닝 연습 하시면 되겠습니다.
이번에는 따라하기 쉽도록 최대한 짧게 잘랐습니다.

공부하는 3단계 방법은 아래와 같습니다.

1분 분량을 번역
전체 듣기 두번
문장 듣고 따라 말하기 두번
한국말로 듣고 영어로 말하기
하루에 한시간 이상 들으면서 말하기 연습하면 좋을 것 같습니다.
연습 mp3 파일 다운로드: https://drive.google.com/open?id=1wrGwsKx4lhjseEUb7B1qzOTpoTb8o01l
원본 동영상:

--- mp3 script & 번역 예 ---
So recursion is just a way of taking a problem and breaking it down into subproblems and then each of those subproblems is generally broken down into more and more and more sub problems. Of course if we did this forever and we didn't have a stopping case, then well we would do it forever. So every recursion must have what's called a base case or like a stopping point. In this case the base case is when we have a folder with no subfolders then we'll just return once we count how many files it has. But let's look at another example. The Fibonacci sequence is one of the simplest examples of recursion. In fact we often say that the Fibonacci sequence is defined recursively. But this definition in and of itself doesn't make a lot of sense. We need a starting point, we need to know what is f of 0 or f of 1. Implementing this recursively is now actually very natural. So this code we'll call fib of n and that will then recur to fib of n minus 1 and fib of n minus 2. Eventually it'll get back those answers and add those up and return that value. When we call say, fib of n minus 1, it'll then do the same thing and recursive and recurse and recurse. We'll stop when we get down to the base cases which are when n is 0 or 1.

--- 번역 예 ---
재귀는 문제를 작은 문제들로 나누고 나눠진 작은 문제들을 다시 작은문제들로 나누어서 처리하는 방법입니다. 계속 하면서 정지 조건이 없으면 영원히 할 수 있습니다. 그러므로 각각의 재귀는 기본 조건 또는 정지점이 있어야 합니다. 이 경우는 하위 폴더가 없으면 그것이 가진 파일 개수를 리턴하면 됩니다.
다른 예제를 봅시다. 피보나치 수열은 가장 간단한 재귀 예제들 중 하나입니다. 사실 피보나치 수열은 재귀적으로 정의 되었다고 자주 얘기합니다. 그러나 이 정의 자체는 많이 이해되지는 않습니다. 우리는 시작점이 필요하고 f0나 f1이 뭔지 알아야 합니다. 이것을 재귀적으로 구현하는 것은 실제적으로 자연스럽습니다. 그래서 이 코드는 fib n 그리고 재귀로 fib n - 1그리고 fib n - 2를 호출할 것입니다. 결국 답들을 돌려주고 그걸 다 합쳐서 결과를 돌려줄 것입니다. Fib n - 1을 호출하고 같은것을 반복할 것입니다. n이 0이나 1일이되는 기초경우까지 가면 정지할 것입니다.

----- 이주의 Interview Question (같이 풀어 봐요!) -----
Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into k non-empty subsets whose sums are all equal.

Example 1:
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Note:

1 <= k <= len(nums) <= 16.
0 < nums[i] < 10000.

원 문제 링크: https://leetcode.com/problems/partition-to-k-equal-sum-subsets/description/