Recursive Algorithm - Recursive Function

Recursive Function

- Recursive(재귀) : 어떤 문제를 해결하기 위해 알고리즘을 설계할 때 동일한 문제의 조금 더 작은 경우를 해결함으로써 그 문제를 해결하는 것

 

- 팩토리얼, 거듭제곱, 문자열 반대로 출력 등의 문제에 적용 가능

---

Java 예시1 - Factorial

 

- Factorial : 자연수 n에 대해서 1부터 n까지의 모든 자연수를 곱한 값

 

- factorial() 함수에 파라미터로 값을 넘길 경우 재귀함수로 반복하여 결괏값을 반환해 주는 함수

 

- factorial(5) = 5 * factorial(4) / factorial(4) = 4 * factorial(3) / factorial(3) = 3 * factorial(2) / factorial(2) = 2 * factorial(1) / factorial(1) = 1 * factorial(0) / factorial(0) = 1

-> factorial(5) = 5 * 4 * 3 * 2 * 1 * 1 = 120

 

- main함수에서 실행한 결과

---

Java예시2 - Factorial

 

- 자연수N 합 계산

 

- sumNaturalNumber() 함수에 파라미터로 값을 넘길 경우 재귀함수를 반복하여 결과값을 반환해 주는 함수

 

- parameter : 5 -> 1+2+3+4+5 = 15 : sumNaturalNumber(5) = 1+2+3+4+5=15

 

- main함수에서 실행한 결과

---

Java 예시3 - POW(거듭제곱)

 

- 거듭제곱(pow) : 하나의 숫자(밑)를 다른 숫자(지수)만큼 곱하는 것

 

- base = 밑, exponent = 지수 2개의 인자를 받아서 거듭제곱을 수행 / Math.pow() 함수가 동일한 기능 수행

 

- 밑의 값 2와 지수값 5를 넣었을 때 2 x 2 x 2 x 2 x 2 값이 되어서 32가 출력

 

- main함수에서 실행한 결과

---

Java 예시4 - ReverseString(문자열 뒤집기)

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

 

 

- main함수에서 실행한 결과

---

C예시 - 추가 예정