[자료구조] 08 재귀호출

✔️ 재귀호출 (recursion)

함수가 실행 중 자기 자신을 다시 호출하는 것 

 

👉 시스템 입장에서는 함수 실행 중에 새로운 함수가 불리는 것과 동일

(프로그래머가 볼 때는 아, 재귀 함수구나! 알 수 있지만 ~)

👉 이럴 때 기존에 수행중인 함수의 context인 지역변수(local variable) , 복귀주소(return address) 등의 정보를 활성 레코드(activation record)에 저장하여 보관하여야 한다 

 

 

❓활성 레코드란?

함수의 환경 정보를 담고 있는 구조체이다. 실행되는 함수마다 1개씩 생성되어 시스템 스택(system stack) 에서 저장, 관리됨

,

❓시스템 스택이란?

함수 호출(procedure call) 을 관리하기 위해 os운영체제에서 사용하는 스택을 말한다. 활성레코드를 저장 

 

 

 

✔️ 대표적인 재귀함수 

 

📌 팩토리얼 

factorial이란 계산 알고리즘, 반복문으로도 구현할 수 있지만 재귀 호출을 사용하면 더 간단하게 알고리즘 기술 가능

n! = 1 * 2 * 3 * ... * (n-1) * n

 

factorial(n)으로 함수를 만들면 

//factorial

#include <stdio.h>

long factorial(int n){
    if (n==0)
        return 1;
    else 
        return n * factorial(n-1);
}

void main(){
    printf("factorial : 10! = %d", factorial(10));
}

//결과 : factorial : 10! = 3628800

 

📌 최대공약수 (greatest common divisor)

정수의 최대공약수는 어떻게 구할까,,?

y> 0 gcd(x,y) = gcd (y,x%y)

y = 0 gcd(x,0) = x

 

ex) gcd(12,16) = gcd(16,16%12) = gcd(16,4) = gcd(4,16%4) = gcd(4,0) = 4

#include <stdio.h>
int gcd(int x, int y);

void main(){
    int x = 12, y =16;
    printf("gcd (%d %d) = %d\n", x, y, gcd(x,y));
}

int gcd(x,y){
    if (y==0) return x;
    else return gcd(y,x%y);
}
//결과 : gcd (12 16) = 4

 

대표적 재귀함수 두개 예시까지 완료!