재귀

재귀 함수(recursive functions)란?

하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것
-생각보다 많은 종류의 문제가 재귀적으로 해결 가능

예: 이진트리(binary trees)

재귀적인 방법을 통해 찾을 수 있음

(이진 탐색과 비슷한 ..트리라는 구조를 이용해서 가능)

보다 간단한 예 - 자연수의 합 구하기
문제: 1부터 n까지 모든 자연수의 합을 구하시오.

-> def sum(n):

     if n <= 1:
         return n

    else:
          return n + sum(n-1)

재귀 호출의 종결 조건

def sum(n):
   if n ...:
            ...
                #매우중요!
   else:
           ...
               sum(...)

-> 알고리즘의 종결 조건에 반드시 필요!

재귀 알고리즘의 효율

def sum(n):

        if n <= 1:
            return n

       else:
             return n + sum(n-1)

:recursive version -> n이 커지면 함수가 호출해야하는 횟수가 증가하기때문에 이 알고리즘은 n에 비례하는 복잡도를 가진다.

->O(n)

def sum(n):
   s = 0

   while n >= 0:
      s+=n
      n -=1

   return s

:iterative version(반복적인 버젼) -> n이 커지면 이것도 역시 n에 비례하는만큼의 순환문 반복때문에, 복잡도는 O(n)과 같음!

​

그런데, 복잡도 측면이 아니라 효율성 측면에서 본다면...

재귀 알고리즘 추가 예제

def what(n):
   if n<=1:
         return 1

   else:
        return n * what(n-1)

이것은 무엇을 구하는 재귀 함수? n!

연습문제 -fibonacci 순열

앞선 두개의 합으로.. 정의되는

iterative version vs recursive version

으로 작성해보기.

(recursive algorithms)

조합의 수 계산
문제: n개의 서로 다른 원소에서 m개를 택하는 경우의 수

def combi(n,m):

   return f(n) / f(m) * f(n-m))

조합의 수 계산 - 재귀적 방법으로
문제: n개의 서로 다른 원소에서 m개를 택하는 경우의 수

def combi(n,m):

  return combi(n-1, m) + combi(n-1, m-1) -->trivial을 고려하지 않음

def combi(n,m):

   if n === m:
      return 1

   elif m == : 0:
      return 1

   else:
      return combi(n-1,m) + combi(n-1, m-1)

->효율성 측면? 두번씩 호출하고있기때문에 상당히 여러분 호출되는면이있다.

효율이 이렇게 떨어지는데 재귀를 왜쓸까?

-> 재귀 알고리즘의 유용성

문제: 하노이의 탑

-> 재귀 알고리즘의 효율

def fibo(n):

   if n<=1:

      return n

   return fibo(n-1) + fibo(n-2)