[알고리즘 공부] #3 재귀(Recursive) 알고리즘 with Python

재귀 알고리즘(Recursive)

어떤 알고리즘일까?

재귀 알고리즘은 하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘을 말한다.

자기 자신을 다시 호출하고 있는 재귀 알고리즘의 모습

위에 사진은 재귀 함수의 작동 방식을 간단한 예제를 활용하여 나타낸 것이다. 사진을 보면 알 수 있듯이 원하는 값을 얻을 때까지 자기 자신을 다시 호출하는 것을 알 수 있다.

 

장점과 단점

• 장점
  재귀 알고리즘은 문제를 작은 단위의 하위 문제로 분활하고, 해당 하위 문제의 해결에도 동일한 알고리즘을 반복적으로 사용함으로 코드가 간결하고 유연성이 높다는 장점이 있다.
• 단점
  재귀 알고리즘은 원하는 값이 나올 때까지 자기 자신을 계속 호출하는 것이기 때문에, 너무 많이 호출할 경우 코드의 속도 저하나 메모리 과다 사용 문제가 발생할 수 있다.

 

언제 사용하는가?

• 재귀적 구조를 가진 문제
  이진 트리의 순회나 피보나치 수열 등 재귀적인 구조를 가진 문제를 해결할 때 사용한다.
• 작업을 작은 단위로 나누어야 할때
  문제를 더 작고 관리하기 쉬운 작은 단위의 하위 문제로 분활해야 할때 재귀 함수를 사용한다. 이렇게 하면 복잡한 문제를 해결하기 쉬운 단위로 쪼개어 해결할 수 있다.

 

알고리즘 사용 예제

1부터 10까지 자연수의 합 구하기

• 문제 설명
  1부터 10까지 자연수의 합을 구하기 위해서는 재귀 함수를 사용하지 않아도 되지만 예시를 위해서 재귀함수를 이용해 구해보도록 하자.
  
  먼저 sum이라는 변수에서 합을 구한다고 지정하고, 1부터 함수를 시작한다. 1을 sum변수에 더한 후 1에 1을 더해서 2를 매개변수로 함수를 다시 호출한다. 그럼 sum변수에 2를 더하고 2에 1을 더해서 3을 매개변수로 함수를 다시 호출한다. 이런식으로 코드를 짜면 10까지의 합을 구할 수 있을 것이다.
  한가지 주의할 점은 11이 매개 변수로 들어왔을 때, 더 이상 함수를 호출하지 않고 return을 해주는 코드를 만들어줘야 한다. 이렇게 함수를 더이상 호출하지 않고 return 해주는 지점을 “base condition” 이라고 한다.
• 알고리즘 사용
  함수 안에서 다시 자기 자신을 호출하는 부분이 재귀함수 알고리즘이 사용된 부분이다.
• CODE
  

def add(num):
    global sum
    if num == 11:
        return
    else:
        sum += num
        add(num + 1)
 
sum = 0
add(1)
print(sum)

---