recursion.md

재귀

피보나치 수열

피보나치 수열은 현재의 수가 이전 두 수의 합으로 이루어진 수열이다. 이 수열에서 n번째 수를 찾기 위해, n-1번째와 n-2번째 수를 재귀적으로 계산하여 합산한다.

function FIBONACCI(n):
  if n이 0이거나 1이면:
    return n
  else:
    return FIBONACCI(n-1) + FIBONACCI(n-2)

하노이의 탑

하노이의 탑은 n개의 디스크를 한 기둥에서 다른 기둥으로 옮기는 문제이다. 재귀적으로, n-1개의 디스크를 보조기둥으로 이동시키고, 가장 큰 디스크를 목표 기둥으로 옮긴 후, 보조 기둥에 있는 n-1개의 디스크를 다시 목표 기둥으로 옮깁니다.

fuction HANOI(n, 시작기둥, 목표기둥, 보조기둥):
  if n이 1이면:
    output "디스크 1을 시작기둥에서 목표기둥으로 이동"
    return
  HANOI(n-1, 시작기둥, 보조기둥, 목표기둥)
  output "디스크 n을 시작기둥에서 목표기둥으로 이동"
  HANOI(n-1, 보조기둥, 목표기둥, 시작기둥)

최소공배수

최소공배수를 구하기 위해 먼저 두 수의 최대공약수(GCD)를 재귀적으로 찾는다. 최대공약수는 유클리드 호제법을 사용해 계산할 수 있다. 최소 공배수는 두 수의 곱을 최대공약수로 나눈 값으로 구할 수 있습니다.

function GCD(a,b):
  if b가 0이라면:
    return a
  else:
    return GCD(b, a % b)

function LCM(a, b):
  return (a * b) / GCD(a, b)

처음으로