[Algorithm] 재귀함수

예제) 명시적인 반복문(For, foreach, while 등)과 외부 라이브러리, 모듈, 함수(sum 등) 사용하지 않고 "안녕하세요"를 n번 반복해서 출력하고, 그다음엔 "끝났습니다"를 출력하여 실행을 종료하는 코드를 작성하시오.

예제를 풀기전에 재귀함수를 알아봅시다.

텍스트 출처 : 나무위키(https://namu.wiki/w/%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98)
그림 : 본인 작성

교수님께 재귀함수가 뭔지 물었더니 계속해서 물어보는 상황이 되어버렸습니다.

"재귀함수가 뭔가요?" 를 말하면 설명해주는 동작이기 때문에
어느순간 "재귀함수가 뭔가요?"를 말하면 다시 또 실행을 하게 됩니다. 그런데, 동작의 끝에서 "재귀함수가 뭔가요?" 라고 말하도록 되어있던 것입니다.

그래서 동작을 끝에 도달했을 때, 또 다시 설명을 시작하게 되고, 또 끝에 도달해서 설명을 시작하게되고, ...

이렇게 무한대로 설명을 해버리는 상황이 발생합니다.
이와 같이 어떤 함수 내에서 자기자신을 다시 참조하는 함수를 말합니다.

---

가장 기본적인 재귀함수를 만들어 보겠습니다.

def function():
	print(”안녕하세요”)
	function()

#실행결과
안녕하세요
안녕하세요
안녕하세요
...

이렇게 함수 내부에서 언제 자기자신을 호출하지 않을지를 정하지 않으면 계속해서 실행되므로, 무한루프에 빠집니다.

그렇다면 3번만 반복하도록 만들려면 어떻게 해야할까요?

def function(a):
    print("안녕하세요")
    if a < 2:
        a += 1
        function(a)
        
function(0)

#실행결과
안녕하세요
안녕하세요
안녕하세요

이렇게 자기자신을 다시 호출하기 전에 값을 검사하는 조건문을 추가하면 됩니다.

---

이를 이해하여 맨처음 보았던 예제의 코드를 짜면 아래와 같습니다.

#재귀함수 기초 : 안녕하세요를 반복하기
def function(a, b):
    if (b - 1 < a):
        print("끝났습니다")
    else:
        print("안녕하세요")
        a += 1
        function(a, b)

function(0, 3)

#출력결과
안녕하세요
안녕하세요
안녕하세요
끝났습니다

function(a, b)는 a가 b-1 보다 크지 않을때 까지 1씩 더하면서 자신을 호출하게 됩니다. 그래서 function(0, 3)은 안녕하세요를 3번출력하고 마지막에 끝났습니다를 출력하게 됩니다.