[바킹독 알고리즘] 재귀

https://blog.encrypted.gg/943?category=773649

재귀

---

재귀란 무엇일까?

: 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘, 즉 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘이다.

절차지향적 사고 vs 귀납적 사고

void func1(int n)
{
	if(n == 0)
		return;
	printf("%d ", n);
	func1(n - 1);
}

n부터 1까지 출력하는 문제를 예를 들어서…

• 절차지향적 사고절차를 따라 출력, 호출을 반복하다가, func1(0) 은 if문에 걸려 재귀를 탈출하게 된다.
• func1(3)의 출력 결과가 어떻게 3 2 1 인가?

• 귀납적 사고만약 func1(k) 가 k k-1 k-2 … 1 을 출력하면 즉 k부터 1까지 차례대로 출력한다면 func1(k+1) 의 경우에는 k+1 k k-1 … 1 을 출력한다는 것을 보여야 한다.결국에는 func1(n) 이라는 함수는 귀납적으로 바라봤을 때, n부터 1까지 차례로 출력하는 함수임을 알 수 있게 되는 것이다.
• 이 상황은 func1(k+1) 이 호출된 때 k+1 이 출력된 이후에 func1(k) 가 호출되고, func1(k) 는 k부터 1까지 차례로 출력이 되는 것이므로,
• 먼저, func1(1) 이 1 을 출력한다는 사실은 굉장히 당연하다.

---

재귀함수의 가장 큰 특징

⇒ 재귀함수는 항상 “탈출 조건"이 필요하다.

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.

재귀에 대한 정보

---

1. 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.재귀는 코드가 간결해지는 대신, 반복문 으로 구현했을 때에 비해 메모리/시간 측면에서 손해를 본다.
2. 모든 재귀는 반복문 만으로 동일한 동작하는 함수를 만들 수 있다.
3. 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다.

   int fibo(int n)
   {
   	if(n <= 1)
   		return 1;
   	return (fibo(n-1) + fibo(n-2));
   }

   이때, fibo(100) 만 된다 하더라도 시간복잡도가 말도 안되게 커져서 손으로 계산하는 것만 못하게 된다.
4. 이러한 문제에 대해서는 재귀대신 DP(다이나믹 프로그래밍)을 사용해서 해결할 수 있다.
5. fibo(3)의 경우 왼쪽에서 이미 계산했지만, 오른쪽에서 또 fibo(3) 을 구하고 있는 것을 볼 수 있다.
6. 이는 재귀가 이미 계산한 것을 또 계산하기 때문이다.
7. 한 예로, 피보나치 함수를 재귀로 구현을 하게 된다면 어떻게 될까?

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

연습문제

---

연습문제 1 - 거듭제곱

1629번: 곱셈

1629번: 곱셈

❌ 오류 코드 (런타임 에러)

#include <stdio.h>

int mul(long long a, long long b, long long m)
{
    long long ans = 1;
    while(b > 0)
    {
        ans = ans * a % m;
        b--;
    }
    return (ans);
}

int main()
{
    long long a, b, m;
    scanf("%lld %lld %lld", &a, &b, &m);
    printf("%d", mul(a, b, m));
    return 0;
}

⭕️ 정답 코드

#include <stdio.h>

int mul(long long a, long long b, long long m)
{
    if(b == 1)
        return (a % m);
    long long ans = mul(a, b/2, m);
    ans = ans * ans % m;
    if(b % 2 == 0)
        return ans;
    return (ans * a % m);
}

int main()
{
    long long a, b, m;
    scanf("%lld %lld %lld", &a, &b, &m);
    printf("%d", mul(a, b, m));
    return 0;
}