[코틀린/Kotlin] 재귀(Recursion)

재귀

• 자기 자신을 호출하는 함수
• 자기 자신을 반복해서 호출하면서 문제를 점점 작게 나누는 방식

구성요소

• 아래 두가지를 필수로 만족해야함

1. 기저 조건(Base case)
   더 이상 자기 자신을 호출하지 않도록 멈추는 조건
2. 재귀 조건(Recursive case)
   자기 자신을 호출하면서 문제를 점점 단순화

예시

• 팩토리얼 계산

fun factorial(n: Int): Int {
    if (n <= 1) return 1                  // 기저조건(base case)
    return n * factorial(n - 1)           // 재귀조건(recursive case)
}

• 예시: factorial(3)

factorial(3) = 3 * factorial(2)
             = 3 * (2 * factorial(1))
             = 3 * (2 * 1)
             = 6

사용 예시

• 크기가 점점 작아지는 반복 작업
• 트리 탐색, DFS, 백트래킹, 분할정복 등의 문제
• 복잡한 반복보다 재귀가 더 직관적일 경우

주의 사항

• 기저 조건이 없을 경우 무한 루프(StackOverflowError)
• 반복보다 성능이 나쁠 수 있음 (호출 스택이 많이 쌓임)

비효율적인 방법 예시

fun fib(n: Int): Int {
    if (n <= 1) return n
    return fib(n - 1) + fib(n - 2)
}

• 같은 계산을 반복하므로 비효율적

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2) ← 중복!
│       ├── fib(1)
│       └── fib(0)
└── fib(3) ← 중복!

• 메모이제이션으로 최적화 가능

🔗 연관 블로그: [코틀린/Kotlin] 메모이제이션(Memoization)

[코틀린/Kotlin] 메모이제이션(Memoization)

 

재귀/반복 비교

방식	설명
반복문	루프 사용 (for, while)
재귀	자기 자신을 호출
공통점	둘 다 반복적인 작업 처리 가능
차이점	재귀는 호출 스택이 쌓임, 종료 조건 필수

문제

1. 정수를 입력 받아 그 수의 팩토리얼을 재귀적으로 계산하는 함수를 작성하세요.

[팩토리얼 정의]

• 0! = 1
• n! = n × (n-1)! (단, n > 0)

[조건]

• 함수 이름은 factorial로 정의합니다.
• 매개변수는 Int형 하나입니다.
• 반환값도 Int입니다.
• 재귀함수로 작성하세요.

답:

fun factorial(n: Int): Int{
	if(n <= 1) return 1
	return n * factorial(n-1)
}

 

 

2. 문자열 str이 주어졌을 때, 재귀함수를 사용하여 문자열을 뒤집는 함수를 작성하세요.

[사용 예시]

reverse("hello") → "olleh"
reverse("abcd") → "dcba"

 

[조건]

• 함수 이름은 reverse로 정의합니다.
• 매개변수는 String형 하나입니다.
• 매개변수 명은 str입니다.
• 반환값도 String입니다.
• 재귀합수로 작성하세요.

 

답:

fun reverse(str: String): String {
	if (str.length == 1) return str
	return reverse(str.substring(1)) + str[0]
}

 

 

보충:

• if(str.length == 1)

빈 문자열이 입력될 경우 substring(1)에서 StringIndexOutOfBoundsException 오류가 발생

→ 재귀 함수는 항상 종료 조건을 넓게 잡는 것이 안전함!

• if(str.length ≤ 1)
• if(str.isEmpty() || str.length ==1)