재귀함수 패캠 강의 공부 내용

아래 두 코드는 흔하고 유명한 알고리즘 문제 2개를 재귀로 풀어본 예다.

 

1. palindrome

def palindrome(string):
    if len(strung) <= 1:
        return True
    
    if string[0] == string[-1]:
        return palindrome(string[1:-1])
    else:
        return False

2. 리스트의 모든 원소의 합 구하기

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

 

 

[재귀 예제:  ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Taejon 2001]

문제: 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 다음과 같이 총 7가지가 있음 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 입력으로 주어졌을 때, n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하시오

힌트: 정수 n을 만들 수 있는 경우의 수를 리턴하는 함수를 f(n) 이라고 하면,
f(n)은 f(n-1) + f(n-2) + f(n-3) 과 동일하다는 패턴 찾기

 

강의자료에 있는 문제 분석 내용을 반드시!!!!!!! 볼 것. 고1 수열 문제에서 봤다는 것을 기억할 것이다.

 

코드:

def func(data):
    if data == 1:
        return 1
    elif data == 2:
        return 2
    elif data == 3:
        return 4
    
    return func(data -1) + func(data - 2) + func(data - 3)