Python 25. 재귀 호출(Recursive call)

이제 파이썬 문법의 마지막까지 달려왔습니다!

 

오늘은 재귀 호출에 대해서 알아보겠습니다. 재귀 호출은 함수 내부에서 자기 자신을 다시 호출하는 행위를 말합니다.

여러 예들을 통해 재귀 호출을 익혀보겠습니다.

 

 

1. 재귀 호출(recursive call)

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘, 고급 정렬 알고리즘 작성시 사용됨

수학 과목 중 확률과 통계라는 과목이 있습니다. 확통 과목에서 순열을 배울 때 저희는 팩토리얼에 대해 배운 경험이 있습니다. 팩토리얼을 이용해서 재귀 호출의 쓰임을 알아보겠습니다.

 

1-1. 재귀 호출 규칙

 

•     n! = n * (n-1)!

 

1-2. 검증

 

순열 계산을 해주는 함수를 생성해보겠습니다.

 

num = 4인 경우

num > 1

return = 4 * factorial(3)

여기서 재귀호출의 개념이 사용되는 것입니다.

factorial(3) 

num > 1

return = 3 * factorial(2)

factorial(2) 

num > 1이므로

return = 2 * factorial(1)

factorial(1) = 1

 

순차적으로 대입하면

factorial (4) = 4 * 3 * 2 * 1 = 4!

입니다.

 

1-3. 재귀호출의 예

• 재귀 함수는 내부적으로 스택처럼 관리
• 파이썬에서 재귀함수의 깊이(한 번에 호출되는)는 1000회 이하로 되어야 함
• 코드분석 툴

Google Colab 종료 중

 

예제를 풀어보겠습니다.

문제

회문(순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미)을 판별할 수 있는 함수를 만들어보자.(재귀 함수를 사용)
        ●  단 회문이면 결과를 True, 아니면 False를 반환

 

    (i) 재귀 함수 사용

 

 

    (ii) 재귀 함수 사용하지 않음

 

 

문제

정수 n을 입력받아 아래와 같이 처리되는 프로그램을 만들어보자.

• n이 홀수면 3*n+1을 함(예: 3입력 -> 10)
• n이 짝수면 n을 2로 나눔(10 / 2 -> 5)
• 이렇게 계속 진행하여 결국 1이 될 때까지 위 조건을 반복하면서 실행

 

 

 

이상으로 파이썬 문법을 모두 살펴보았습니다.

까먹지 않도록 틈틈이 꺼내서 기억해둡시다!