재귀함수

재귀함수란?

함수가 자기 스스로를 호출하는 함수.

반복문(for문, while문) 없이 반복문처럼 동작한다.

그러나 스택 오버 플로우(함수를 끝내지 않고 또 함수를 호출하는 것을 반복하면 콜스택의 저장 공간이 부족해짐)가 날 수 있기 때문에 조심해야 한다.

재귀함수를 사용하면 큰 문제를 작은 하위 문제들로 쪼갤 수 있다.

 

 

<재귀 함수 구성>

-베이스 케이스: 더 작은 문제들로 쪼갤 필요 없이, 답이 나와 있는 경우

-재귀 케이스: 더 작은 하위 문제들로 쪼개야 하는 경우

 

재귀 함수 만드는 법

하위 문제를 찾는다 -> 베이스 케이스와 재귀 케이스를 정한다 -> 함수를 구현 한다.

 

재귀함수를 기준으로

재귀함수 위는 먼저 실행

재귀함수 아래는 나중에 실행

 

ex) 각 자리 수의 합 더하기

하위 문제: 마지막 자리 수 제외 나머지 자리 수를 더함 -> 마지막 자리 수를 더함
베이스 케이스: n이 일의 자리일 때 (n<10)
재귀 케이스 : n > 10

 

마지막 자리 수 제외 하는 법: n // 10

마지막 자리 수 구하는 법: n % 10

def sumDigit(n):
    if n < 10:
        return n
    return sumDigit(n // 10) + (n % 10)

 

2023.09.16 - [Python] - [Python] 재귀함수를 이용한 리스트 최대, 최소 값 찾기

[Python] 재귀함수를 이용한 리스트 최대, 최소 값 찾기

 

2023.05.26 - [Python] - [Python] 재귀함수 삼각수

 

2023.09.12 - [분류 전체보기] - [자바스크립트] 재귀함수를 사용한 팩토리얼 함수 만들기

[자바스크립트] 재귀함수를 사용한 팩토리얼 함수 만들기