[알고리즘] 재귀

재귀(Recursion)

• 함수 안에서 동일한 함수를 호출하는 것

예시

• 팩토리얼(!) 구하기
• 회문(palindrome): 거꾸로 읽어도 제대로 읽는 것과 같은 단어, 숫자 등

예시(팩토리얼) 구현

• 함수 factorial(n)은 $n!$ 을 반환한다고 하자
  • 수학시간에 했던 $f(n)$ = $n!$ 처럼 생각하면
• 2! = 1 $\times$ 2 = factorial(2)
• 3! = 1 $\times$ 2 $\times$ 3
  • = factorial(2) $\times$ 3
  • = factorial(3)
• 4! = 1 $\times$ 2 $\times$ 3 $\times$ 4
  • = factorial(2) $\times$ 3 $\times$ 4
  • = factorial(3) $\times$ 4
  • = factorial(4)

일반화

• n! = factorial(n-1) $\times$ n

결론

• factorial(n) = factorial(n-1) $\times$ n
• factorial(n) 함수는 factorial(n-1) $\times$ n을 반환하면 된다.
• n <= 1 일때는 1을 반환.(0!은 1로 정의하기 때문)

특징

• 점점 작아지는 구조
• 언젠간 끝나게 해야한다
• 재귀는 스택이다(LIFO)

  • ex	$4!$
    	여기서부터 쌓임
    	4 $\times$ $f(3)$
    	4 $\times$ $f(3)$	3 $\times$ $f(2)$
    	4 $\times$ $f(3)$	3 $\times$ $f(2)$	2 $\times$ $f(1)$	$f(1) = 1$
    				여기서부터 빠짐
    	4 $\times$ $f(3)$	3 $\times$ $f(2)$	2 $\times$ 1
    	4 $\times$ $f(3)$	3 $\times$ 2
    	4 $\times$ 6 $=$ 24

---

Python

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

Swift

func factorial(_ n: Int) -> Int {
    if n > 1 {
        return factorial(n-1) * n
    } else {
    	return 1
    }
}