강의

https://www.youtube.com/watch?v=8vDDJm5EewM&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=12

설명

재귀 함수는 base condition이 있어야 함!
base condition으로 수렴하는 형태가 돼야 함.

모든 재귀함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음.

재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 봄.

한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음

피보나치 재귀로 푸는 경우를 보면 이미 계산한 문제를 또 계산하는 경우가 발생함.

재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적 됨.

주의

문제

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x0B.md

1629

모듈러 곱셈 성질을 알고 있어야 함

https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-multiplication

성질을 이용해서 지수를 1/2씩 낮춰가며 재귀를 사용해줌. 그럼 O(log n)이 됨.

y = f(k / 2)로 생각하기. 절차적 말고 귀납적으로 생각하기.

11729

하노이의 탑 문제
하.. 완전 까먹었었다

점화식: $a_1 = 1, ... , a_n = 2a_{n-1} + 1$
일반항: $a_n = 2^n - 1$
일반항 증명: https://mgyo.tistory.com/185

1074

1,2,3,4분면으로 나눌 수 있음
n을 1씩 줄여가는 재귀함수를 사용하면 됨

걍 외우기...

17478

재귀 들어가기 전에 있는 코드랑, 들어갔다 나온 후 코드의 차이 익히기 좋은 문제

1780

베이스 컨디션: 해당 범위가 모두 같은 글자일 때
이외에는 9구역으로 나눈 범위를 재귀로 타고 들어감

시작점을 나눈 범위의 시작좌표로 해줌

2630

1780이랑 똑같은 문제

1992

1780이랑 똑같은 문제. 출력만 어떻게 할지 고민하면 됐는데 재귀 들어가는 for문 전에 여는 괄호 출력하고, 다 마치고 나서 닫는 괄호 출력했음.

2447

와우 옛날에 이거 고민하다 머리 터지는 줄 알았는데 강의 듣고 앞 문제들 푸니까 넘 쉽게 풀어진다😮
메모리 넉넉하니까 배열 선언하고 9구역씩 나누면서 재귀로 들어가주면 됐다
1 2 3
4 5 6
7 8 9
중에 5는 건너뛰고 1, 3, 4, 6, 7, 9 구역만 재귀로 들어가면서 n == 1이 될 때 * 을 찍어주면 됐음

2448

아!! 배열 선언할 때 j 범위를 2 * N - 1으로 해주어야 한다!!