[알고리즘] 재귀함수 (Recursive Function)

---

재귀함수

재귀함수란 함수 내에서 자기 자신을 호출하여 작업을 수행하는 방식의 함수이다.

재귀함수를 작성할 때는 함수 내에서 자기 자신을 다시 호출한 후, 그 함수가 끝날 때까지 함수 호출 이후의 명령문이 수행되지 않는다는 사실과 종료조건이 꼭 포함되어야한다는 부분을 인지하고 작성하면 오버플로우를 피할 수 있다.

 

다시말해

재귀함수에서 중요한 부분은 실행을 마무리짓는 부분과, 계속 재귀를 실행하는 부분이 존재한다는것이다. 또한 그것이 일반적으로는 n이 0이나 1이 되면 종료하게 되게끔 구성이 되어있다.

 

 

 

---

1. 카운트다운

def countdown(n) :
    # 0 이 되는순간 end 출력
    if n==0 :
        print("end")
    
    # 받은 인자 출력 및, n-1 한값을 다시 재귀
    else :
        print(n)
        countdown(n-1, sep="\n")

if __name__ = "__main__" :
    countdown(10)

10
9
8
7
6
5
4
3
2
1
end

#코드가 진행되는 과정

countdown(10)
->

print(10)
 countdown(9)
  print(9)
   countdown(8)
    print(8)
     countdown(7)
      print(7)
       countdown(6)
        print(6)
         countdown(5)
          print(5)
           countdown(4)
            print(4)
             countdown(3)
              print(3)
               countdown(2)
                print(2)
                 countdown(1)
                  print(1)
                   countdown(0)
                    print("end")

---

2. 구구단

내림차순과 오름차순 두가지로 나눠 출력해보도록 하자.

2-1. 내림차순 구구단

def mul(n)
    if n==0 :
        print("end")
    else :
        print("2 * {} = {}".format(n, 2 * n))
        mul(n-1)
        
if __name__ == "__main__"
    mul(10)

# 결과

2 * 9 = 18
2 * 8 = 16
2 * 7 = 14
2 * 6 = 12
2 * 5 = 10
2 * 4 = 8
2 * 3 = 6
2 * 2 = 4
2 * 1 = 2
end

일반적인 재귀함수는 매개변수가 작아지다가 0이 되면 끝나는 형태라 위의 구구단도 내림차순의 형태로 되어있다.

 

2-2. 오름차순 구구단

def mul(n)
    if n==0 :
        print("end")
    else :
        mul(n-1)
        print("2 * {} = {}".format(n, 2 * n))
        
if __name__ == "__main__"
    mul(10)

# 결과

end
2 * 1 = 2
2 * 2 = 4
2 * 3 = 6
2 * 4 = 8
2 * 5 = 10
2 * 6 = 12
2 * 7 = 14
2 * 8 = 16
2 * 9 = 18
2 * 10 = 20

우리 눈에 익숙한 오름차순 구구단이다.

위에서 언급했던것처럼, 재귀함수는 함수 내에서 자기 자신을 다시 호출한 후, 그 함수가 끝날 때 까지 그 다음 명령문이 수행되지 않는다는것을 명심해야한다.

#코드가 진행되는 과정

mul(10)
->
 mul(9)
  mul(8)
   mul(7)
    mul(6)
     mul(5)
      mul(4)
       mul(3)
        mul(2)
         mul(1)
          mul(0)
           print("end")
          print("2 * 1 = 2")
         print("2 * 2 = 4")
        print("2 * 3 = 6")
       print("2 * 4 = 8")
      print("2 * 5 = 10")
     print("2 * 6 = 12")
    print("2 * 7 = 14")
   print("2 * 8 = 16")
  print("2 * 9 = 18")
 print("2 * 10 = 20")

else문을 자세히 보면, 출력보다 재귀가 앞에 있는것을 알 수 있다.

즉, 숫자가 작아지면서 재귀를 먼저 진행하고 n이 0이 되어서 재귀함수가 다시 돌지 않게 될 때 쌓여있던 print문들을 실행한다.

 

print문과 재귀함수의 위치에 따라 결과가 아예 달라질 수 있기 때문에, 신중하게 코드를 작성하여야한다.

---

3. 팩토리얼

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

if __name__ == "__main__"
    print(factorial(5))
    

#결과

120

factorial(5)
->
return 5 * factorial(4)
 factorial(4)
 ->
 return 4 * factorial(3)
  factorial(3)
  ->
  return 3 * factorial(2)
   factorial(2)
   ->
   return 2 * factorial(1)
    factorial(1)
    ->
    return 1
   return 2 * 1
  return 3 * 2 * 1
 return 4 * 3 * 2 * 1
return 5 * 4 * 3 * 2 * 1

 

---

4. 피보나치 수열

피보나치 수는, 첫째 및 둘째 항이 1이며 그 뒤의 모든 항이 바로 앞 두 앞 항의 합인 수열이다.

 

처음 여섯 항은 각각 1, 1, 2, 3, 5, 8 이다. 편의상 0번째 항을 0으로 두기도 한다.

 

2020.10.16 - [<공부>/[Algorithm]] - [Algorithm] 피보나치 수열(Fibonacci Sequence) 알고리즘 (JAVA)

[Algorithm] 피보나치 수열(Fibonacci Sequence) 알고리즘 (JAVA)

쓰다말았지만 기본적인 개념들과 여러가지 방법들을 어느정도 써놨기에... 참고하면 좋을듯

 

 

#삼항연산자 사용
def fibo3(n) :
    return fibo(n-1) + fibo(n-2) if n >= 2 else n

#일반
def fibo(n) :
    if n >= 2 :
        return fibo(n-1) + fibo(n-2)
    else :
        return n        

if __name__ == "__main__" :
    for i in range(1, 11) :
        print(i, fibo(i))

#실행 결과
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55

#코드가 진행되는 과정 (6 이상은 생략)

# i == 1
fibo(1)
->
return 1

# i == 2
fibo(2)
->
return fibo(1) + fibo(0)
 return 1 + 0

# i == 3
fibo(3)
->
return fibo(2) + fibo(1)
 return ( fibo(1) + fibo(0) ) + fibo(1)
  return ( 1 + 0 ) + 1
  
# i == 4
fibo(4)
->
return fibo(3) + fibo(2)
 return ( fibo(2) + fibo(1) ) + ( fibo(1) + fibo(0) )
  return ( ( fibo(1) + fibo(0) ) + 1 + 1 + 0
   return 1 + 0 + 1 + 1 + 0
   
# i == 5
fibo(5)
->
return fibo(4) + fibo(3)
 return ( fibo(3) + fibo(2) ) + ( fibo(2) + fibo(1) )
  return ( ( fibo(2) + fibo(1) ) + ( fibo(1) + fibo(0) ) ) + ( ( fibo(1) + fibo(0) ) + 1 )
   return ( ( ( fibo(1) + fibo(0) ) + 1 ) + 1 + 0 + 1 + 0 + 1
    return 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1
    
    
...

n이 0이나 1일 때는 값도 0, 1이기 때문에 그대로 반환하면 되고, 2 이상일 때만 재귀 함수 두개로 분기해 값을 반환한다.

 

시간 복잡도는 함수가 한번 호출되면 중첩되어 다시 두번 호출되기때문에 지수적으로 증가하게 되어 O(2^n)이 된다.