[알고리즘] 재귀함수 - 팩토리얼 구하기

* <모두의 알고리즘 with 파이썬>의 문제 04를 정리한 내용입니다.

 

 

1. 재귀함수를 사용한 팩토리얼 구하기

• 설명: 재귀함수를 사용하여 n! 팩토리얼 값을 출력한다. 예를 들어 n=9라면, 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 의 값을 구해야 한다. 
• 주의 해야하는 포인트: 
  • 재귀함수 사용시, 반드시 종료 조건을 작성해야 한다.
  • 재귀함수를 사용하면 매 호출 함수 관련 정보가 메모리에 계속 쌓이게 된다. 함수가 최종 return 값을 반환해야 스택이 비워지는데, 함수가 끝나지 않고 계속 계속 함수가 재귀적으로 호출됨으로써 함수의 깊이는 계속 깊어진다. 이 과정에서 계속 메모리가 쌓이게 되고 그래서 stack overflow가 일어난다. 

 

 

2. 재귀함수 (recursive function)

• 재귀 함수란 어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수를 의미한다.

 

 

3. 알고리즘 풀이 

3.1 팩토리얼을 구하는 알고리즘

def factorial(n): 
    if n == 1: 
        return n
    return n * factorial(n-1)

 

3.2 문제 1의 1부터 n까지의 합 구하기를 재귀호출로 만들어보세요 

def find_sum(n):
	if n == 1:
    	return n
    return n + find_sum(n-1)

 

3.3 문제 2의 숫자 n개 중에서 최댓값 찾기를 재귀호출로 만들어보세요 

def find_max(x, y):
    if x > y : 
        return x
    else: 
        return y


def max_array(array, leng):  
    if leng == 1:
        return array[0]    
    else: 
        return find_max(array[leng-1], max_array(array, leng-1))


temp_array = [1, 33, 4, 56, 123, 509, 23, 66]
print(max_array(temp_array, len(temp_array)))

•