반드시 알아야하는 알고리즘 top 8 - 1. 재귀 알고리즘

 

반드시 알아야 하는 알고리즘 top 8 

• 재귀 알고리즘 

• 이진 탐색 

• 순차 탐색

• 버블 정렬

• 삽입 정렬

• 탐욕 알고리즘

• 최단거리 알고리즘

• 몬테 카를로 알고리즘

재귀 함수 

• 재귀함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미합니다. 다른 말로는 재귀호출, 되부름이라고 부르기도 합니다. 반복문을 사용하는 코드는 항상 재귀함수를 통해 구현하는 것이 가능하며 그 반대도 가능합니다.

• 재귀함수를 작성할 때는 함수내에서 다시 자신을 호출한 후 그 함수가 끝날 때 까지 함수 호출 이후의 명령문이 수행되지 않는 다는 사실과 종료조건이 꼭 포함 되어야한다는 부분을 인지하고 작성하면 무한루프를 방지할 수 있습니다.

재귀 함수 예제 01 - Countdown 

def countdown(n):

    if n == 0 :

        print("boom")

    else:

        print(n)

        countdown(n-1, end=' ')

    

countdown(10)

• 결과값 : 10 9 8 7 6 5 4 3 2 1 boom

• countdown 함수는 재귀함수의 가장 기초적인 예제 중 하나 입니다. 이 코드가 진행되는 과정을 한번 살펴보겠습니다.

• 처음 countdown(10) 이 실행되면 n 이 10이기 때문에 if 문이 아닌 else 문이 실행됩니다. print(10) 과 countdown(9) 가 실행되고 count(9) 는 print(9) 와 countdown(8) 을 실행하며 이렇게 계속 진행하다가 결국 countdown(0) 을 실행하고 n이 ㅇ이 되어 print("boom") 을 실행하며 마치는 흐름으로 진행됩니다.

재귀 함수 예제 02 - 구구단 출력 

def multi_table_2(n):

    if n==0:

        print('end')

    else:

        print('2 * {} = {}'.format(n,2*n))

        multi_table_2(n-1)

    

multi_table_2(9)

• 결과값 :

• 구구단 2단을 재귀함수로 구해보는 예제 입니다. 하지만 일반적인 재귀함수는 매개변수가 작아지다가 0이 되면 끝이나는 형태기 때문에 출력된 구구단도 큰수부터 작아지는 형태로 구성되어 있습니다. 이를 작은 수부터 출력하는 방법을 알아보겠습니다.

재귀 함수 예제 03 - 구구단 출력2 

def multi_table_2(n):

    if n==0:

        print('end')

    else:

        multi_table_2(n-1)

        print('2 * {} = {}'.format(n,2*(n)))

multi_table_2(10)

• 결과값 : 

• 우리가 평소에 사용하는 오름차순 구구단이 실행되는 것을 볼 수 있습니다. 위에서 정의한 것 처럼 재귀함수는 함수내에서 다시 자신을 호출한 후 그 함수가 끝날 때 까지 함수 호출 이후의 명령문이 수행되지 않는다 라는 사실을 알아야 합니다. 

• 이 코드를 풀어보면 다음과 같습니다. 

• 숫자가 작아지면서 함수를 지속적으로 재귀하다가 n 이 0이 돼서 더이상 재귀하지 않을 때 재귀함수 다음에 있는 print 문들을 실행하기 시작합니다.  단순히 print 문의 위치에 따라 결과가 상이해지기 때문에 재귀함수를 사용할 때는 코드 한 줄 한 줄 잘 살펴나가야 합니다.

재귀 함수 예제 04 - 팩토리얼 

def factorial(n):

    if n==1:

        return 1

    else:

        return n * factorial(n-1)

print(factorial(5))

• 결과값 : 120

• 팩토리얼 또한 매우 일반적인 재귀함수의 예제 입니다. 위의 예제들과 다른 부분이 있다면 return 을 사용해서 구성하는 부분일까요.

• 이 코드도 같이 한번 따라가 보겠습니다.

• 여러 예제들을 보면서 패턴을 찾아내신 분도 있으시겠지만, 재귀함수에서 중요한 부분은 함수가 더이상 실행되지 않게 하는 조건부와 계속 실행되게 하는 조건부가 존재한다는 부분입니다. 또한 그것이 일반적으로는 n 이 0이나 1이 되면 종료하게 되게끔 구성이 되어있습니다.

• 팩토리얼 함수 또한 n 이 1이 되면 종료하게 구성되어 있습니다. 이 부분이 위에서 설명한 종료조건을 꼭 신경쓰면서 코드를 작성해야한다는 부분입니다.

---

부족한 블로그에 방문해 주셔서 감사합니다.

잘못된 부분이나 질문이 있으시면 

댓글로 말씀해주세요.

금방 확인하고 피드백 드리겠습니다.

좋은 하루 되세요. ^^