1. 순환

1-2 순환적으로 사고하기

• 문자열 길이 계산

  • 1char씩 정벅하며 순환

  • 순환의 단위가 k(0부터 시작)번째 단어 n이 될때까지 순환

• 2진수로 변환하여 출력

  • 2로 나눌 때마다 나머지 출력

• 모든 순환함수는 반복문으로 변경 가능

• 그 역도 성립. 모든 반복문은 recursion으로 표현 가능

• 순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현

• 하지만 함수 호출에 따른 오버헤드가 있음(매개변수 전달, activation frame 생성 등)

1-3 순환 알고리즘 설계

• 적어도 1개의 base case, 순환되지 않고 종료되는 case 있어야 함

• 즉 모든 case는 base case로 수렴한다

리커시브하게 문제 풀 때 원칙

1. 일단 전부 다 해봐야할 거 같으면 순환 함수의 단위를 나눠서 리커시브하게 단계별로 풀어나가야함

2. 리커시브가 해결하는게 개수 인지 bool 인지 결정

3. 모든 case는 결국 base case로 수렴

4. 암시적 매개변수가 아닌 명시적 매개변수가 있어야 함.

미로 찾기

• 1개 셀에 대해서 동,서,남,북으로 리커시브하게 방문

  • 위 네 방향에서 true를 1개라도 리턴하면 출구 찾음

• basecase는

  • 벽이거나 return false

  • 방문했거나 return false

  • 출구라면 return true

cell

현재 픽셀이 속한 blob의 크기 카운트 하기

• 현재 셀의 대각선, 동서남북(8개 case)를 차례대로 방문

  • 각 리커시브 함수는 방문하며 누적된 개수를 리턴

• basecase는

  • 셀의 크기를 벗어나거나

  • 방문한 곳

n-queens

n-queens 케이스 찾아서 출력하기

• 전부다 방문하며 정답 케이스 1가지 찾기

  • 조건에 맞는 정답을 찾아야 함

  • 전부 다 방문하며 조건에 맞는 것만 기록해야하기 때문에 백트래킹(DFS) 이용

• 리커시브 함수는 방문한 셀이 조건에 맞는지 확인

  • 조건 맞지 않으면 return 하여 그다음 셀을 인자로 함수 호출

  • 조건 맞으면 다음 행에 대해 리커시브 함수 진행

• basecase

  • 조건에 맞지 않거나

  • 현재 방문한 셀이 조건 충족 && 마지막 행일 경우

powerset

모든 멱집합 출력하기

• 모든 케이스 구하는 문제

• 멱집합은 부분집합 1개를 선택 하거나 안하거나 2가지 케이스에 대해 상태 트리 그린것

• 리커시브 함수는 2가지 케이스를 진행

  • 선택하거나

  • 선택안하거나

• basecase

  • 모든 케이스를 선택한 경우 출력