재귀함수

재귀함수에 대해 알아보자.

 

재귀함수란 자기 자신을 다시 호출한다는 의미....

 

자기자신을 다시 호출하는데 파라미터를 바꿔가면서 호출한다.

 

여기서 무한정 자기자신을 호출할 수 있기에 종료조건은 필수로 필요하다.

 

그리하여 반복계산할수있도록 하는 것..

 

이렇게만 말하면 헷갈리니..예제 코드를..

 

def factorial(n: int) -> int:
    # 종료조건
    if n <= 1:
        return 1

    return n * factorial(n-1)


print(factorial(4))

Output:
24

 

간단한 팩토리얼 함수이다.

 

파라미터를 int값으로 받는..

 

사용자는 factorial(4)를 원하고 4라는 값이 파라미터로 전달되고

 

factorial 함수 내에서는 종료조건으로 입력받은 파라미터가 1일때 종료. 그 이외에는 또 다시 재귀함수로 n-1값이 들어가는

 

저식을 디버깅 해보면 결국 n값은

 

n = 4 * 3 * 2 * 1의 값이 들어갈 것이다.

 

 

추가로 최댓수를 찾아보는 예제를 알아보자

 

def max(x: int, y: int) -> int:
    if x > y:
        return x
    else:
        return y


def max_array(array: int, len: int) -> int:
    if len == 1:
        return array[0]
    else:
        return max(array[len - 1], max_array(array, len - 1))


temp_array = [33, 44, 5, 66, 139, 390, 45, 23]

print(max_array(temp_array, len(temp_array)))

Output:390

 

재귀함수를 이용하여 배열내에 있는 최대값을 찾는것이다.

 

기존 배열에서 max_array라는 함수와 max라는 함수를 이용하여 가장 큰 값을 비교한다.

 

디버깅을 해보면

 

1:  33과 44를 비교  : 최대값 44

2:  44와 5를 비교 : 최대값 44

3: 44와 66을 비교  : 최대값 66

4: 66과 139를 비교 : 최대값 139

5: 139와 390을 비교 : 최대값 390

 

이런 순서로 값이 계산되어 진다.

 

재귀가 복잡하긴한데..... 잘 사용하면 참 좋고...아니면..괜히 디버깅하기 어려운 함수일수 있기에..사용하기 참 애매한 알고리즘인것 같다.