파이썬 재귀호출로 반복문 줄이기

이미지 출처: 코딩도장

알고리즘은 효율적인 패턴을 찾아내어 문제를 해결하는데 도움을 준다.

앞으로 그 알고리즘을 하나하나 배우면서 문제를 풀어나가려고 한다.

 

첫번째로 재귀호출에 대해서 공부해보았다.

 

알고리즘 문제를 풀 때, 복잡한 수식을 생각하기전에 단순하게 모든 경우의 수를 계산해보는 방법이 있다.

이를 완전탐색이라고하는데, 이 때 재귀함수를 사용하면 간단하게 해결할 수 있다.

 

재귀호출이란?

자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수

 

반복문을 재귀호출 이용하도록 바꿔보자!

문제) 1~N까지의 수를 더해주는 함수

ex) numbers=5 -> 1+2+3+4+5

 

1) 반복문 사용

def is_sum(N):
    sum_num = 0
    for i in range(1,N+1):
        sum_num += i
    return sum_num

 

2) 재귀호출 사용

def is_sum(N):
    if N == 1:
        return 1
    return N + is_sum(N-1)

리턴에서 함수를 다시 호출하는데, N은 이번에 처리하고 다음 작업을 넘겨준다 (N-1) 

중요한건, 언제 멈출지를 꼭 정해줘야하는것!

for 문에서 언제 멈출지를 정해주는것처럼, 재귀호출 사용할 때도 언제까지 불러줄지 꼭 써주어야한다.

위 코드에서는 N이 1일때 또 재귀함수를 호출하면 is_sum(0)을 호출하고, 그 다음에는 is_sum(-1)를 호출하기 때문에,

if N==1:  return 1  이라는 조건을 추가해서 재귀호출을 멈춰준다.

 

재귀호출 문제 풀이

문제 출처 -코딩도장

파이썬 코딩 도장: 31.4 연습문제: 재귀호출로 회문 판별하기

문제설명

재귀호출을 사용해서 회문을 판별하자. 

ex) 'level' > True, 'discribe' > False, 'Tenet' > True

def is_palindrome(word):

    if len(word) < 2:
        return True
        
    if word[0] == word[-1]:
        return True * is_palindrome(word[1:-1])
    else:
        return False

1) 작은단위 어떻게 쪼개서 일할지 정의하기

2) 언제 재귀호출 멈출지 정해주기

 

위의 순서로 문제를 풀었다.

먼저, 문자열의 맨 앞과 맨 뒤의 글자를 비교하는 작업을 수행하고

다음 호출문에서 2번째 글자와 맨 뒤에서 2번째 글자를 비교하는 작업을 수행한다.

그러다가 비교해야할 글자가 없을 때 함수호출을 멈추어준다!

 

알아야 할 개념

1) 논리연산

True * True = True

True * False = False

False * False = False

 

2) 문자열 슬라이싱

t = 'abcdefg'

t[0] = 'a'

t[-1] = 'g'
t[1:-1] ='bcdef'

t[>=:<] -> 앞에 오는 인덱스는 포함하고, 뒤에 오는 인덱스는 포함하지 않음