hello-algo/ko/codes/dart/chapter_computational_complexity/recursion.dart

/**
 * File: recursion.dart
 * Created Time: 2023-08-27
 * Author: liuyuxin ([email protected])
 */

/* 재귀 */
int recur(int n) {
  // 종료 조건
  if (n == 1) return 1;
  // 내려가기: 재귀 호출
  int res = recur(n - 1);
  // 돌아오기: 결과 반환
  return n + res;
}

/* 반복으로 재귀 구현 */
int forLoopRecur(int n) {
  // 명시적인 스택을 사용하여 시스템 호출 스택을 모방한다
  List<int> stack = [];
  int res = 0;
  // 내려가기: 재귀 호출
  for (int i = n; i > 0; i--) {
    // 스택에 삽입하여 내려가는 과정을 모방한다
    stack.add(i);
  }
  // 돌아오기: 결과 반환
  while (!stack.isEmpty) {
    // 스택에서 꺼내어 돌아오는 과정을 모방한다
    res += stack.removeLast();
  }
  // res = 1+2+3+...+n
  return res;
}

/* 꼬리 재귀 */
int tailRecur(int n, int res) {
  // 종료 조건
  if (n == 0) return res;
  // 꼬리 재귀 호출
  return tailRecur(n - 1, res + n);
}

/* 피보나치 수열: 재귀 */
int fib(int n) {
  // 종료 조건 f(1) = 0, f(2) = 1
  if (n == 1 || n == 2) return n - 1;
  // 재귀 호출 f(n) = f(n-1) + f(n-2)
  int res = fib(n - 1) + fib(n - 2);
  // 결과 f(n)을 반환한다
  return res;
}

/* 실행 코드 */
void main() {
  int n = 5;
  int res;

  res = recur(n);
  print("\n재귀 함수로 구한 합 res = $res");

  res = tailRecur(n, 0);
  print("\n꼬리 재귀 함수로 구한 합 res = $res");

  res = forLoopRecur(n);
  print("\n반복으로 재귀를 구현하여 구한 합 res = $res");

  res = fib(n);
  print("\n피보나치 수열의 항(n = $n) = $res");
}