소개
재귀
재귀 함수는 스스로를 호출하는 함수예요.
_재귀 함수_에는 적어도 하나의 _기저 사례_와 적어도 하나의 _재귀 사례_가 있어야 해요.
기저 사례는 함수를 다시 호출하지 않고 값을 반환해요.
재귀 사례는 입력을 바꿔서 언젠가는 기저 사례에 맞게 만든 뒤 함수를 다시 호출해요.
다음은 배열의 원소 개수를 세는 예제예요.
def count:
if length == 0 then
0 # base case
else
1 + (.[1:] | count) # recursive case
end;
([] | count), # => 0
([11, 22, 33] | count) # => 3
_재귀 함수_는 여러 개의 _기저 사례_를 가질 수도 있고, 여러 개의 _재귀 사례_를 가질 수도 있어요.
예를 들어 피보나치 수열은 두 개의 _기저 사례_를 가진 재귀 수열이에요.
def fibonacci:
if . == 0 then
0
elif . == 1 then
1
else
(. - 1 | fibonacci) + (. - 2 | fibonacci)
end;
10 | fibonacci # => 55
배열에서 주어진 값 x가 몇 번 나오는지 세는 함수에는 두 개의 _재귀 사례_가 있어요.
def count_occurrences(x):
if length == 0 then
0
elif first == x then
1 + (.[1:] | count_occurrences(x))
else
(.[1:] | count_occurrences(x))
end;
[11, 22, 33, 22, 44] | count_occurrences(22) # => 2
실제로는 배열이나 그 밖의 열거 가능한 자료 구조를 순회할 때는 map, reduce 같은 내장 함수를 쓰거나 [.[] | select(...)]처럼 스트림을 이용하는 경우가 가장 많아요.
내부적으로는 일부 내장 함수가 재귀를 사용해 구현되어 있어요.
지침
jq 기반 데이터 파이프라인을 유지보수하는 팀에 막 합류했어요. 첫 페어 프로그래밍 세션에서 새 동료가 궁금해해요: "add, reverse, map이 내부에서는 어떻게 동작하는지 알아요? 한번 살펴봐요, 내장 함수를 쓰지 말고 재귀로 직접 구현해 봐요."
1. 배열의 숫자를 더하는 함수 구현하기
재귀를 연습하기 위해 내장 add 필터를 다시 구현해 볼 거예요.
_기저 사례_는 빈 배열의 합이 0이라는 거예요.
내장 add를 쓰지 말고 재귀 함수로 직접 구현해 봐요.
[5, 4, 6, 10] | array_add # => 25
2. 배열 뒤집기
내장 reverse 필터를 다시 구현해 볼 거예요.
_기저 사례_는 빈 배열을 뒤집으면 빈 배열이 나온다는 거예요.
내장 reverse를 쓰지 말고 재귀 함수로 직접 구현해 봐요.
[5, 4, 6, 10] | array_reverse # => [10, 6, 4, 5]
3. 배열 매핑하기
내장 map 필터를 다시 구현해 볼 거예요.
이 함수는 필터를 매개변수로 받아서, 입력 배열의 각 원소에 그 필터를 실행하고, 그 결과를 새 배열에 담아 반환해요.
_기저 사례_는 빈 배열을 매핑하면 빈 배열이 나온다는 거예요.
내장 map을 쓰지 말고 재귀 함수로 직접 구현해 봐요.
[5, 4, 6, 10] | array_map(. + 10) # => [15, 14, 16, 20]
학습 연습 문제
