[알고리즘 스터디 with 케이시] 재귀함수

Tags: 알고리즘
등록일: 2022.08.03
블로그 포스팅 여부: In progress
비고: 클로저 캡쳐, 함수형 프로그래밍을 공부하고 나서 다시 보자.
작성소요시간: 0:30
학습일: 2022.08.03

정의

• 자기 자신을 호출하는 함수를 말한다.
  • 자기 자신을 호출하는 것을 재귀 호출(Recursion call)이라고 합니다.
• 함수 호출은 Call stack 에 쌓이기 때문에 스택 자료구조와 유사하게 동작합니다.
• 함수형 프로그래밍에선 루프 구현을 재귀로 구현하는 경우가 많습니다.
• 잘못 작성하면 무한 루프에 빠질 수 있습니다.
• 재귀로 작성하면 더 쉽게 풀리는 코딩 테스트 문제가 있다.
  • 더 효율적인 것은 아님

재귀로 구현해야 편한 알고리즘

• Union-Find
• DFS
• Backtracking

사용법

• 재귀 함수를 작성할 때는 반드시 탈출 할 수 있는 조건을 작성해야 한다.
  • 보통 if 등 조건을 통해 탈출한다.

탈출 조건을 작성해두어야 한다.

피보나치 수열

• 앞 두 항의 합이 뒤 항의 값이 되는 수열
• 재귀를 설명할 때 자주 등장한다.

 

// 피보나치 수열
// 1 1 2 3 5 8 13
func fibonacci(num: Int) -> Int {
    if num <= 2 {
        return 1
    }
    return fibonacci(num: num - 1) + fibonacci(num: num - 2)
}
print(fibonacci(num: 7))        // 13

피보나치 7 은 피보나치 6과 피보나치 5의 합으로 구성됩니다.

우측 트리는 생략하고 좌측트리를 계속 타보겠습니다.

탈출 조건이 있기 때문에 피보나치 1과 2에서 멈출 수 있었네요.

이제부터 역으로 올라가 보도록 하겠습니다.

합병 정렬에서 분할과 합병도 재귀를 통해 쉽게 구할 수 있습니다.

자바스크립트로 구현한 합병 정렬

• 스위프트로 구현한 합병정렬

import Foundation

func merge(_ a: [Int], _ b: [Int]) -> [Int] {
    if a.isEmpty {
        return b
    } else if b.isEmpty {
        return a
    } else if a[0] < b[0] {
        return [a[0]] + merge(Array(a[1..<a.count]), b)
    } else {
        return [b[0]] + merge(a, Array(b[1..<b.count]))
    }
}

func mergesort(_ arr: [Int]) -> [Int] {
    if arr.count < 2 {
        return arr
    } else {
        let mid = arr.count / 2
        return merge(mergesort(Array(arr[..<mid])), 
                                         mergesort(Array(arr[mid..<arr.count])))
    }
}

print(mergesort([21, 10, 12, 20, 25, 13, 15, 22]))

• 자바스크립트로 구현한 합병 정렬

const generateColumn = (index, last) =>
  index === 0 || index === last.length
    ? 1
    : last[index - 1] + last[index];

const generateColumns = (columns, index, last) =>
  index === last.length + 1
    ? columns
    : generateColumns(
      [...columns, generateColumn(index, last)],
      index + 1,
      last
    );

const generateRows = (rows, n) =>
  n === 0
    ? rows
    : generateRows(
      [...rows, generateColumns([], 0, rows[rows.length - 1])],
      n - 1
    )

const pascalTriangle = (n) => generateRows([[1]], n - 1);

console.log(pascalTriangle(3)); // [[1], [1, 1], [1, 2, 1]]