재귀적으로 사고하기
기본 사례와 재귀 단계를 배워 보세요.
재귀적으로 사고하기은(는) CoddyKit의 무료 Scala for Backend Engineering & Functional Programming 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Scala for Backend Engineering & Functional Programming 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Scala for Backend Engineering & Functional Programming 강의에는 총 4개의 강의가 포함되어 있습니다.
재귀란 무엇인가
재귀란 함수가 같은 문제의 더 작은 형태를 해결하기 위해 자기 자신을 호출하는 것입니다.
Scala에서 재귀는 변경 가능한 변수 없이 반복을 표현할 수 있으므로 함수형 프로그래밍에 자연스럽게 어울립니다.
모든 재귀 함수에는 두 가지가 필요합니다. 멈추는 방법과 문제를 더 작게 만드는 방법입니다.
기저 사례부터 시작하기
기저 사례는 추가 재귀 없이 함수가 직접 답할 수 있는 가장 단순한 입력입니다.
기저 사례가 없으면 함수가 자신을 영원히 호출하다가 스택 오버플로로 중단됩니다.
항상 재귀 단계보다 먼저 기저 사례를 설계하세요.
def countdown(n: Int): Unit =
if (n < 0) () // base case: stop
else {
println(n)
countdown(n - 1) // recursive step
}첫 번째 재귀 함수
다음은 1부터 n까지의 수를 더하는 완전한 프로그램입니다.
기저 사례는 0을 반환하고, 재귀 사례는 n과 그보다 작은 모든 수의 합을 더합니다.
def sum(n: Int): Int =
if (n == 0) 0
else n + sum(n - 1)
@main def run(): Unit =
println(sum(5)) // 15호출 추적하기
재귀를 이해하려면 호출을 손으로 전개해 보세요.
sum(3)은 3 + sum(2)가 되고, 이는 3 + 2 + sum(1)이 되며, 다시 3 + 2 + 1 + sum(0)이 됩니다.
sum(0)이 0을 반환해야만 이 호출 사슬이 하나의 값인 6으로 다시 합쳐집니다.
// sum(3)
// = 3 + sum(2)
// = 3 + (2 + sum(1))
// = 3 + (2 + (1 + sum(0)))
// = 3 + (2 + (1 + 0))
// = 6목록에서 재귀 사용하기
목록은 본질적으로 재귀적입니다. 목록은 비어 있거나(빈 목록), 머리와 그보다 작은 꼬리로 이루어집니다.
이 구조는 재귀 함수에 그대로 대응됩니다. 빈 목록이 기저 사례이고, 머리에 꼬리에 대한 재귀 호출을 적용하는 것이 재귀 단계입니다.
def length[A](xs: List[A]): Int = xs match {
case Nil => 0
case _ :: t => 1 + length(t)
}꼬리 패턴 매칭하기
:: 패턴은 비어 있지 않은 목록을 머리와 꼬리로 나눕니다.
각 재귀 호출은 엄밀히 더 짧은 목록을 대상으로 하므로 빈 목록을 향해 반드시 진행합니다.
이는 Scala에서 목록을 재귀적으로 순회하는 표준적인 방법입니다.
def sumList(xs: List[Int]): Int = xs match {
case Nil => 0
case h :: t => h + sumList(t)
}
@main def run(): Unit =
println(sumList(List(1, 2, 3, 4))) // 10두 번의 재귀 호출
일부 문제는 하나보다 많은 재귀 호출로 분기됩니다.
대표적인 예가 피보나치로, 각 값이 앞의 두 값에 의존합니다.
이 단순한 버전은 같은 값을 여러 번 다시 계산하므로 이해하기는 쉽지만 느립니다.
def fib(n: Int): Int =
if (n < 2) n
else fib(n - 1) + fib(n - 2)
@main def run(): Unit =
println(fib(7)) // 13스택 비용
각 재귀 호출은 호출 스택에 프레임을 추가하며, 내부 호출이 반환될 때까지 기다려야 합니다.
재귀가 매우 깊어지면 스택이 소진되어 StackOverflowError가 발생할 수 있습니다.
단순한 크기가 아니라 깊이를 세면 이러한 위험을 예측하는 데 도움이 됩니다.
// This would overflow the stack for large n:
// def deep(n: Int): Int =
// if (n == 0) 0 else 1 + deep(n - 1)
// deep(1000000) // StackOverflowError기저 사례를 향해 줄이기
재귀의 핵심 불변식은 모든 호출이 기저 사례에 더 가까워져야 한다는 것입니다.
인수가 더 작아지지 않거나 종료 조건에 도달하지 않으면 재귀는 끝나지 않습니다.
실행하기 전에 이를 확인하세요.
def reverse[A](xs: List[A]): List[A] = xs match {
case Nil => Nil
case h :: t => reverse(t) :+ h // t is smaller than xs
}재귀와 반복문 비교
명령형 코드는 변경 가능한 카운터와 while 반복문을 사용하고, 함수형 코드는 변경할 수 없는 값과 재귀를 사용합니다.
둘 다 같은 계산을 표현할 수 있지만, 재귀는 데이터의 구조를 더 직접적으로 설명합니다.
Scala에서는 원시적인 반복문보다 재귀나 고차 함수를 선호하는 경우가 많습니다.
// Imperative
var total = 0
for (i <- 1 to 5) total += i
// Recursive
def sum(n: Int): Int = if (n == 0) 0 else n + sum(n - 1)재귀 해법 설계하기
신뢰할 수 있는 절차는 다음과 같습니다. 기저 사례를 식별하고, 더 작은 입력에 대한 재귀 호출이 이미 작동한다고 가정한 다음, 머리와 그 결과를 결합합니다.
이러한 도약이 재귀적 사고의 핵심입니다. 더 작은 호출을 신뢰하고 한 단계만 처리하는 것입니다.
def maxOf(xs: List[Int]): Int = xs match {
case h :: Nil => h
case h :: t => math.max(h, maxOf(t))
}
@main def run(): Unit =
println(maxOf(List(3, 9, 2, 7))) // 9빠른 확인
재귀 구조에 대한 이해를 확인해 보세요.
복습
재귀는 문제를 자기 자신의 더 작은 사례로 줄여 해결합니다.
모든 재귀 함수에는 멈추기 위한 기저 사례와 입력을 그 기저 사례를 향해 줄이는 재귀 단계가 필요합니다.
빈 목록과 머리-꼬리 구조를 지닌 목록은 재귀적 사고를 연습하기에 이상적입니다. 매우 큰 입력에서는 스택 깊이를 주의하세요.
자주 묻는 질문
“재귀적으로 사고하기” 강의는 무료인가요?
네 — “재귀적으로 사고하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Scala for Backend Engineering & Functional Programming 강의 전체를 잠금 해제할 수 있습니다. Scala for Backend Engineering & Functional Programming 강의에는 총 4개의 강의가 포함되어 있습니다.
“재귀적으로 사고하기”에서 뭘 배우나요?
기본 사례와 재귀 단계를 배워 보세요. 브라우저에서 직접 실행하는 실습 코드로 Scala for Backend Engineering & Functional Programming을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Scala for Backend Engineering & Functional Programming을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Scala for Backend Engineering & Functional Programming은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“재귀적으로 사고하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Scala for Backend Engineering & Functional Programming 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Scala for Backend Engineering & Functional Programming 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- 재귀적으로 사고하기
- 누산기 패턴
- foldLeft와 foldRight
- reduce와 집계