[자료구조와 알고리즘] 재귀

지수·2021년 9월 1일

자료구조와 알고리즘

목록 보기

9/12

재귀 함수 : 내 속엔..내가 너무도 많ㅇr..

📖 재귀란?

✅ 자신의 정의할 때 자기 자신의 재참조하는 방법
✅ 프로그래밍에서는 재귀 호출의 형태로 많이 사용
(위키백과, 재귀)

ㄴ 재귀 = 자기 안에서 자기 또 부르는 반복 구조

ㄴ 흔한 프로그래밍 속 재귀 = 재귀 함수

1. 재귀 함수

: 재귀 함수란 어떤 함수 안에서 자기 자신을 다시 호출하여 작업을 수행하는 방식의 함수(=되부름)
이미지 출처 : 위키백과, 재귀

2. 재귀 함수 구조

재귀 함수는 반복적으로 자기 자신을 호출하는 구조를 가졌기 때문에 자칫 잘못하면 무한 루프에 빠질 위험이 있다.

(무한 루프에 빠지지 않도록) 재귀 종료 조건
재귀
그 외 내부 진행 코드

재귀 함수를 쓸 때에는 상단에 종료 조건을 필수적으로 명시해주어, 무한 루프에 빠지지 않도록 한 다음
아래에서 해당 종료 조건에 해당하지 않을 경우 수행할 재귀(자기 자신 함수)를 명시하고
그 외 추가적인 진행 코드가 필요하다면 이를 필요한 위치에 배치한다.

또한 재귀 함수의 경우,
함수 내에서 자기 자신을 호출한 후 해당 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 점을 고려해야한다.
[이미지 출처 : 플레이데이터 알고리즘 특강, 재귀]

3. 재귀 함수 사용 이유

ㄴ 코드 간결화 및 변수 사용 최소화

재귀함수로 짤 수 있는 코드를 재귀 없이 짠다면...
수많은 반복문의 굴레..그 안의 i, j, k, .......⭐

4. 재귀 함수 사용 대표 예시(자바)

1) 팩토리얼

public static int factorial(int n) {
        if (n <= 1) { 
       	   return 1; 
        }
        else { 
           return n * factorial(n-1); 
        }
    }

2) 피보나치 수열

public static int fibonacci(int n) {
        if (n <= 1) { 
           return n; 
        }
        else { 
           return fibonacci(n-1) + fibonacci(n-2); 
        }
    }

5. 자바 최대 재귀 깊이는!?

💡 재귀 깊이(recursion depth) : 가장 처음하는 호출을 포함한 중첩 호출(재귀 호출)의 최대 개수

파이썬의 경우 최대 재귀 깊이가 1000이라서 그 이상의 재귀를 호출하면 Recursion Error 발생
위의 에러가 발생하는 경우 아래 코드를 통해 최대 재귀 깊이 조정 가능

import sys
sys.setrecursionlimit(조정할 최대 깊이)

그렇다면 자바는??

자바의 최대 재귀 깊이는 <최신 JVM & default 설정> 기준 대략 10,000이라고 합니다. (출처 : java limit for recursion)
+) 그런데 또 stackoverflow에서 해당 수치가 매번 다르다는 의견이 있었습니다.. (출처 : stackoverflow, What is the maximum depth of the java call stack?)