재귀

난이도 쉽게
자주 묻는 질문 아마존 인포시스 MAQ
재귀 스택 이론조회수 97

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

재귀 란 무엇입니까?

재귀는 단순히 자신을 호출하는 함수로 정의됩니다. 이전에 해결 된 하위 문제를 사용하여 더 큰 문제를 계산합니다.

이것은 프로그래밍에서 가장 중요하고 까다로운 개념 중 하나이지만 재귀를 실제 예제와 연결하려고하면 쉽게 이해할 수 있습니다.

거울 앞에 거울을 놓을 때의 상황을 생각하십니까?

재귀

이것은 거울이 거울을 반사하기 때문에 발생합니다. 그것은 거울을 반사하는 것입니다.

이것이 바로 재귀가하는 일입니다.

이제 재귀가 어떻게 작동하는지 시각화 해 보겠습니다.

모든 모서리에 삼각형을 그리는 함수를 정의하면. 그 결과를 상상할 수 있습니까?재귀

위의 두 가지 예에서 우리는 끝이없는 하위 문제를 보았습니다 (거울은 서로를 계속 반사하고 무한한 수의 거울이있는 것처럼 보이며 두 번째 예에서는 숫자가 무한히 계속 증가합니다).

이것으로 우리는이 무한한 구조를 피할 모든 재귀 함수에 대한 종료 조건이 필요함을 이해합니다. 이 상태는 다음과 같이 알려져 있습니다. 기본 케이스.

재귀 형성 단계

  1. 기본 케이스
  2. 더 작은 문제에 대한 재귀 호출
  3. 해결 된 하위 문제를 사용하여 더 큰 문제 계산

예를 들어 이해해 보겠습니다.

질문 : 1로 시작하는 n 연속 자연수의 합을 계산합니다.

int sum(int n){

    // Base Case

    if(n==1){

        return n;

    }

    else{

        int smallerSum=sum(n-1);      //recursive call for smaller problem

        return n+smallerSum;         // solve bigger problem using solved smaller sub-problems

    }

}

재귀 및 스택

기능 호출되면 메모리를 차지합니다. 스택 함수 실행에 대한 세부 정보를 저장합니다. 그리고 기능이 종료되면 그 기능이 차지하는 메모리도 해제됩니다. 이제 재귀에서는 함수가 자체적으로 호출된다는 것을 알고 있습니다. 따라서 모든 함수 호출에서 현재 실행중인 함수의 정보를 보관하기 위해 스택에 메모리 블록이 생성됩니다. 함수가 종료되면 외부 함수에 작성된 호출 문으로 돌아갑니다. 즉, 외부 함수가 중지 된 위치에서 다시 시작됩니다. n = 3에 대한 위의 예에서 메모리 구조를 보겠습니다.

재귀와 스택의 연관성을 염두에두면 Base Case가 없으면 프로그램이 스택 오버플로 및 시간 제한 초과로 어려움을 겪게된다는 것을 쉽게 이해할 수 있습니다.

직접 재귀와 간접 재귀의 차이점

직접 재귀

  1. 동일한 함수가 자신을 호출하면 다음과 같이 알려져 있습니다. 직접 재귀.
  2. Direct Recursion에서 호출 및 호출 된 함수는 동일합니다.
  3. 한 단계의 재귀 호출이 있습니다.

Direct Recursive 함수의 코드 구조 :

return_type func_name(arguments)
{
  // some code...

  func_name(parameters);

  // some code...
}

간접 재귀

  1. 함수가 부모 함수를 직접 또는 간접적으로 호출하는 다른 함수를 호출하면 다음과 같이 알려져 있습니다. 간접 재귀.
  2. 간접 재귀에서는 호출 및 호출 된 함수가 다릅니다.
  3. 다단계 재귀 호출이 있습니다.

간접 재귀 함수의 코드 구조 :

return_type func_name1(arguments)
{
  // some code...

  func_name2(parameters);

  // some code...
}

return_type func_name2(arguments)
{
  // some code...

  func_name1(parameters);

  // some code...
}

재귀 유형

  1. 꼬리 재귀
    • 함수의 마지막 실행 문이 재귀 호출 일 때.
    • 스택에서 마지막 재귀 호출 만 유지할 수 있습니다.
    • 예:
int sum(int n,int &ans){
    if(n==0){
        return ans;
    }
    else{
        ans=ans+n;
        return sum(n-1,ans);     // last statement to be executed is recursive call

    }
}
  1. 꼬리없는 재귀
    • 재귀 적 호출 문 이후에 실행할 명령문이 함수에 남아있을 때.
    • 재귀 호출은 평가가 끝날 때까지 스택에 남아 있습니다.
    • 예:
int sum(int n){
    if(n==1){
        return n;
    }
    else{
        int smallerSum=sum(n-1);      //recursive call for smaller problem
        return n+smallerSum;         //statements to be executed after recursive call
    }
}

반복을 통해 재귀를 사용하는 경우

두 방법 모두 장단점이 있으므로 특정 문제를 해결하기 위해 어떤 방법을 사용해야하는지 이해해야합니다.

재귀는 문제를 해결하기위한보다 직관적 인 접근 방식입니다. 분할 및 정복 예를 들어, 반복적 인 접근 방식을 사용하여 때때로 수행하기 어려운 하위 문제로 문제를 재귀 적으로 계속 나눌 수 있으므로 병합 정렬과 같습니다. 트리 순회(Inorder, Preorder, Postorder). 그러나 여러 함수 호출의 오버 헤드가 없기 때문에 반복적 접근 방식이 재귀보다 빠르다는 것도 사실입니다.

참고 : 문제를 해결하기 위해 반복이나 재귀 또는 둘 다를 사용할 수 있습니다.

재귀는 명시 적 호출 스택이있는 반복으로 대체 될 수있는 반면 반복은 tail_recursion으로 대체 될 수 있습니다. 프로그래머로서 우리는 메모리와 시간 최적화를 통해 코드를 쉽고 깔끔하게 작성하는 것 사이의 균형을 만들어야합니다.

다른 질문을 해결해 보겠습니다.

n의 계승을 계산합니다.

C ++ 구현

#include <iostream>
using namespace std;
int fact(int n){
   // Base Case
   if (n <= 1)
        return 1;
   else 
       return n*fact(n-1);    
}
int main(){
   int n=5;
   cout<<fact(n);
   return 0;
}
Output: 15

자바 구현

class Main{  
 static int fact(int n){    
  if (n<=1)    
    return 1;    
  else    
    return(n * fact(n-1));    
 }    
 public static void main(String args[]){  
  int n=5;   
  System.out.println(fact(n));    
 }  
}
Output: 15

읽어 주셔서 감사합니다!!

계속 지켜보고 다른 블로그도 확인하십시오. 수정 / 제안이 있으면 댓글을 달아주세요.

참조

균열 시스템 설계 인터뷰
Translate »