⚫️ 재귀함수

DFS와 BFS를 이해하기 위해서 재귀를 필수적으로 이해해야한다. 나는 아직 재귀함수를 어떻게 돌려서 결과값을 찾으면 되겟다! 싶은 감이 아직 없다….. 어떻게 다들 이걸 그렇게 빨리빨리 머리회전을 하시는것인지..

재귀함수란, 자기 자신을 다시 호출하는 함수를 의미한다. (쳇 이건 나도 알아)

작은문제를 해결하고 큰 문제를 해결하는 것이 재귀 아이디어의 핵심이다.
재귀는 반드시, 탈출조건이 있어야 한다.

▪️ 대표 알고리즘 구현해보기

라이브 코딩에서 ‘팩토리얼’ 혹은 ‘피보나치 수열’ 알아요? 그거 구현한번만 해볼래요? 이런식으로 진행되는 경우도 있다. (주변에서 그랬었음!) 그래서 대표적으로 어떻게 구현할 것인지 알아두는 것도 중요할 것 같다.

🔖 팩토리얼 함수 구현하기

반복문으로 구현하기

func factorial(num: Int) -> Int {
    var result = 1

    for i in 2...num {
        result *= i
    }
    return result
}

재귀로 구현하기

재귀 아이디어는 아래 그림과 같다. 작은 문제들을 먼저 해결해주면서 차례대로 올라오면 된다.

func factorial(num: Int) -> Int {
    if num == 1 {
        return 1
    }

    return num * factorial(num: num-1)
}

🔖 피보나치 수열 구현하기

수열 1, 1, 2, 3, 5,,, 를 구현했고 num에 알고싶은 위치 index를 넣으면 그 수를 알려준다

반복문으로 구현하기

func fibonacci(num: Int) -> Int {
    if num == 1 || num == 2 {
        return num
    }

    var a = 1
    var b = 1
    var result = 0

    for _ in 3...num {
        result = a + b
        a = b
        b = result
    }

    return result
}

재귀로 구현하기