Recursive Call (재귀함수, 재귀호출)

재귀함수는 매우 많은 알고리즘에서 사용된다. 앞으로 다룰 quick sort와 merge sort 알고리즘을 공부하기 전, 이 알고리즘들에 쓰이는 전략인 Dynamic Programming(동적 계획법)과 Divide and Conquer(분할 정복)에 대해 공부하기 위하여 오늘은 재귀함수를 공부하여 보겠다. 즉, quick sort와 merge sort를 공부하기 위해 DP와 DC를 공부해야하고 이를 위해서는 기본적인 재귀함수(재귀호출/재귀용법/recursive call)을 알아야한다... ㅎㅎ(앞으로 더 배워야 할 알고리즘들이 많으니 기쁜 마음으로 차곡차곡 공부를 해보자^0^/)

 

📌재귀 함수 recursive call

재귀 함수란, 함수가 본인 함수를 다시 호출하는 함수를 말한다.

 

📌재귀 함수의 일반적인 형태

형태1

def function(입력):
    if 입력 > 일정값:
        return function(입력-1)
    else:
        return 일정값, 입력값 또는 특정값

return function(입력-1): 물론 1이 아닌 다른 수를 연산해 줄 수도 있다.(직관적으로 보기 위하여 편의상 -1을 빼주었다.) 결국, 앞의 입력보다 더 작은 값, 즉 일정값에 더 가까워지는 값이 나오도록 하면 된다.

 

형태2

def function(입력):
    if 입력 <= 일정값:
        ruturn 일정값, 입력값, 또는 특정값
    function(입력-1)
    reuturn 결과값

형태2는 사실 형태1과 사실상 같다. if문의 부호만 반대로 써서 순서만 바꾼 것이다. 역시 마찬가지로, 재귀호출을 할 때에는 function(입력-1)에서 1이 아닌 다른 수를 연산해 주는 것이 가능하다. 일정값에 더 다가갈 수 있도록 입력값을 줄여주기만 하면 된다.

 

✔️예제1) factorial

def factorial(num):
    if num <= 1:
        return num
    return num * factorial(num-1)

 

✔️예제2) 1부터 num까지의 곱

def multiple(num):
    if num <= 1:
        return num
    return num * multiple(num-1)

 

✔️예제3) list의 합을 return

def sum_list(data):
    if len(data) <= 1:
        return data[0]
    return data[0] + sum_list(data[1:])

 

✔️예제4) 회문palindrome 판단

회문palindrome은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미한다.

회문을 판별할 수 있는 함수를 리스트 슬라이싱과 재귀용법을 이용하여 만들어보자.

def palindrome(sting):
    if len(string) <= 1:
        return True

    if string[0] == string[-1]:
        return palindrom(string[1:-1])
    else:
        return False

 

✔️예제5) 홀수 짝수

정수 n에 대해 n이 홀수이면 3xn+1을 하고, n이 짝수이면 n을 2로 나눈다. n이 1이 될 때까지 이를 반복하는 코드를 재귀함수를 이용해서 만들어보자.

def function(num):
    if num == 1:
        return num
    if n%2 == 1:
        return function(3*num+1)
    else:
        return function(n/2)

 

✔️예제6) 정수n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수

def function(data):
    if data ==1:
        return 1
    elif data == 2:
        return 2
    elif data ==3:
        return 4

    return funcion(data-1) + function(data-2) + function(data-3)

 

📌재귀함수는 대표적인 stack

함수는 내부적으로 stack처럼 관리된다.

재귀함수에서, 가장 마지막에 쌓인 것부터 값이 return되는 데 그 return된 값이 다시 함수로 들어가서 또다시 return되기를 반복한다.

이 재귀함수 부분을 공부하며 한가지 의문이 생긴 것이 있다.바로 if문을 쓸 때 else는 어떤 경우에 쓰고, 어떤 경우에 쓰지 않아도 되는 것인가..?