99클럽 코테 스터디 13일차 TIL + 재귀 함수

학습 키워드

- 재귀 함수

 

공부한 내용

재귀 함수

• 재귀 함수는 함수 내부에서 ‘자기 자신을 호출’하는 함수를 의미한다. 이를 통해서 함수가 자신을 반복적으로 호출하면서 원하는 결과를 도출할 수 있다.

→ 일정 조건을 만족하는 경우 자신을 호출하는 것을 말한다.

• ! 재귀함수를 사용하는 경우 함수 호출이 계속 쌓이기 때문에 호출 스택이 많아져서 성능이 저하될 수 있다. 따라서 재귀함수를 작성할 때는 무한루프에 빠지지 않도록 종료 조건을 명확하게 설정해야 한다.

재귀 함수의 특징

• 자기 자신을 호출하는 방법으로 문제를 해결한다.

Base case(기본 경우)와 Recursive case(재귀적인 경우)로 구분된다.

Base case(기본 경우) : 재귀 호출을 멈추는 조건을 나타낸다.

Recursive case(재귀적인 경우) : 재귀 호출이 반복적으로 일어나는 부분이다.

재귀 함수의 장단점

장점

• 코드의 가독성이 높아진다. 재귀적인 호출을 통해 코드를 간결하게 작성할 수 있다.
• 일부 알고리즘에서는 반복문을 사용하기 보다는 재귀 함수를 사용하는 것이 더 직관적이다.

단점

• 재귀 함수는 함수를 호출할 때마다 스택에 새로운 프레임을 생성한다. 따라서, 스택이 너무 깊어질 경우에 스택 오버 플로우가 발생할 수 있다.
• 재귀 함수는 함수의 호출이 반복적으로 일어나기 때문에, 일반적으로 반복문을 사용하는 것보다 느리다.

재귀 함수를 활용한 예시

1. 팩토리얼 계산 방법

• 팩토리얼은 자연수 n에 대해서 1부터 n까지의 모든 자연수를 곱한 값을 의미한다.
• 팩토리얼은 factorial() 함수에 파라미터로 값을 넘길 경우 재귀함수로 반복하여 결괏값을 반환해 주는 함수이다.

1. N 자연수의 합 계산 방법

• sumNaturalNumber() 함수에 파라미터로 값을 넘길 경우 재귀함수를 반복하여 결괏값을 반환해 주는 함수이다.
• 5라는 값을 파라미터로 넘겼을 때 아래와 같이 호출이 된다. 1+2+3+4+5의 결과값인 15를 반환한다.

⇒ sumNaturalNumber(5)는 1+2+3+4+5=15 가 된다.

1. 거듭제곱(pow) 계산

• 하나의 숫자(밑)를 다른 숫자(지수)만큼 곱하는 것이다.

1. 문자열 뒤집기

• reverseString() 함수를 통해 문자열의 값이 0이 되면 문자열을 반환하고 그렇지 않으면 첫 번째 문자를 마지막 문자와 바꾸고 나머지 문자열에 대해 reverseString() 함수를 재귀적으로 호출한 결과를 반환한다.

재귀 함수를 이용한 알고리즘 : 피보나치 수열, 유클리드 호제법, 이진 탐색, 이항 계수

1. 피보나치 수열 : 경우의 수 계산

• 이전 두 항의 합이 다음 항이 되는 수열을 의미한다. 즉, 첫째 항과 둘째 항이 1이고 이후 모든 항은 바로 앞 두항의 합으로 이루어지는 수열을 의미한다.
• 피보나치 수열의 예로는 [1, 1, 2, 3, 5, 8, 13, 21, 34,...]과 같은 형태로 구성된다.

1. 유클리드 호제법 알고리즘 : 최대공약수 계산

• 두 수의 “최대공약수(GCD)”를 찾기 위한 알고리즘을 의미한다.
• 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될 때까지 작동하는 방법을 의미한다. 그 때 작은 수가 최대공약수이다.

1. 이진 탐색(Binary Search) 알고리즘

• 정렬된 배열에서 원하는 데이터를 빠르게 찾기 위한 알고리즘이다.
• 이진탐색은 배열의 중간값을 선택한 후, 찾고자 하는 데이터와 중간값을 비교한다. 만약 중간값이 찾고자 하는 데이터보다 크면, 중간값의 왼쪽 부분 배열에서 다시 중간값을 선택하여 비교한다. 반대로 중간값이 찾고자 하는 데이터보다 작다면, 중간값의 오른쪽 부분 배열에서 다시 중간값을 선택하여 비교한다. 이 과정을 반복하여 원하는 데이터를 찾는다.
• 이진탐색은 데이터의 개수가 많을 때도 빠르게 데이터를 찾을 수 있기 때문에 많이 사용되는 알고리즘 중 하나이다.

1. 이항계수(binomial theorem) 알고리즘

• 조합론에서 사용되며, n개의 서로 다른 원소에서 r개의 원소를 선택하는 경우의 수를 의미한다.

 

회고

발생한 문제

- 자료구조를 공부하다가 재귀 함수에 대한 공부가 필요하다고 생각했다. 

 

해결 방법

- 재귀 함수에 대한 공부를 했다. 

 

알게된 내용

- 재귀 함수를 활용한 예시로는 팩토리얼 계산 방법, N 자연수의 합 계산 방법, 거듭제곱 계산, 문자열 뒤집기가 있고, 재귀 함수를 이용한 알고리즘에는 피보나치 수열, 유클리드 호제법, 이진 탐색, 이항 계수가 있다. 

 

추후 학습할 내용

- 제너릭이나 자료구조 트리에 대한 공부를 진행할 것 같다. 

 

 

참고 자료

- https://velog.io/@ssuh0o0/JavaAlgorithm-%EC%9E%AC%EA%B7%80%ED%98%B8%EC%B6%9C

- https://woogong80.tistory.com/126