이 섹션의 지식 포인트:

1. 반복의 정의:

a. 귀속은 수학적으로 나누어 자치하는 사상으로 귀속은 대형 복잡한 문제를 원래의 문제와 같지만 규모가 작은 문제로 바꾸어 처리한다.
b. 귀속 함수: 즉 함수 자체가 자신의 함수를 호출한다.
   c.
귀환은 경계 조건이 있어야 한다. 경계 조건이 만족하지 않을 때 귀환은 계속 진행되고 경계 조건이 만족할 때 귀환은 멈춘다!
   d.
귀환에 주의해야 할 문제: 귀환 층수가 끊임없이 증가하는 과정에서 프로그램 창고가 넘칠 위험도 끊임없이 커진다!!!

2. 피폴라치 수열 귀속 해법:

코드 예:

#include <stdio.h>
#include <stdlib.h>


int fibonacci(int n)
{
	if(n > 1)
	{
		return (fibonacci(n-1) + fibonacci(n-2));
	}	
	else if(1 == n)
	{
		return 1;
	}
	else if(0 == n)
	{
		return 0;
	}
} 

int main(int argc, char *argv[])
{
	
	int i = 0;
	for(i = 1; i <= 10; i++)
	{
		printf("fibonacci(%d) = %d
", i, fibonacci(i));
	}	
	return 0;
}

주의: 피폴라치 수열은 그 자체가 하나의 귀속 수열이기 때문에 귀속 공식을 직접 찾을 수 있다.이 귀속 알고리즘에서 n=1과 n=0은 귀속 출구다!

3.strlen 반복 해법:

코드 예:

#include <stdio.h>

int strlen(const char* s)
{
	if(NULL == s)
	{
		return -1;
	}
	if('\0' == *s)
	{
		return 0;
	}
	return (strlen(s+1) + 1);	
}
int main()
{
	printf("%d
",strlen("12345"));
	printf("%d
",strlen(NULL));
	printf("%d
", strlen(""));
	return 0;	
}

주의: 사실return은 층마다 귀속 함수에 1을 추가할 뿐입니다!

4. 역방향 출력에 재귀속 사용:

   a.
역귀함수는 일반적으로 외부에서 내부로 들어가고 내부에서 외부로 차례대로 튀어나오기 때문에 역방향 출력 문제를 처리하기에 적합합니다!!!
코드 예:

#include <stdio.h>

void reverse(const char* s)
{
	if(NULL != s)
	{
		if('\0' == *s)
		{
			printf("
");
		}
		else
		{
			reverse(s+1);
			printf("%c",*s);
		} 
	}
}

int main()
{
	reverse("12345");
	printf("
");
	return 0;
}

5. 한노타 귀속 해법:

a. 한노타 알고리즘에 있어서 이런 귀속은 좀 어려워요!먼저 여기서 논의하는 것은 세 기둥의 한노타이다. 한노타의 구체적인 규칙은 작은 것은 영원히 큰 위에 있고 한 번에 한 접시만 움직일 수 있다!
b. 알고리즘 분석:
세 기둥에 대해 우리는 각각 기점, 중간 변수, 목표라고 부른다!우리의 목적은 바로 기점 위의 n개의 접시를 중간 변수를 거쳐 목표로 이동하는 것이다!우리는 이를 간소화하여 기점의 n-1개의 접시를 중간 변수로 옮긴 다음에 기점의 마지막 접시를 목표로 옮긴 다음에 중간 변수의 n-1개의 접시를 목표로 옮길 수 있다!이렇게 하면 우리의 귀속 모델이 만들어져서 n-1을 계속 찾고 한 접시만 있는 상황에서 바로 기점에 있는 한 접시를 목표로 이동합니다!이게 바로 역귀출구!!!

#include <stdio.h>

/*n ，a ，b ，c */ 
void hanoi(int n, char a, char b, char c)
{
	if(1 == n)// ，  
	{
		printf("%c -> %c
",a,c);
	} 
	else
	{
		hanoi(n-1, a, c, b); // n-1 a c b  
		
		printf("%c -> %c
",a,c);  // n a c  
	
		hanoi(n-1, b, a, c);  // b n-1 a c  
	} 
}
int main()
{
	hanoi(3,'a','b','c'); 
	return 0;
}

주의: 이 안에서 분명히 고려할 만한 것은 매번 소위 말하는 출발점, 중간 변수, 목표라는 개념은 모두 상대적이다!!!

6. 전체 배열 문제의 귀속 해법:

코드 예:

#include <stdio.h>

/*s   a    b */
void permutation(char* s, int a, int b)
{
	int i = 0; 
	if((NULL != s) && (b >= a) && (a >= 0))
	{
		if(a == b)
		{
			printf("%s
",s);
		}
		else
		{
			for(i = a; i <= b; i++)
			{
				char c = s[i];
				s[i] = s[a];
				s[a] = c;
				
				permutation(s, a+1, b);
				
				char d = s[i]; //     
				s[i] = s[a];
				s[a] = d;
				
				
			} 
		} 

	} 
}

int main()
{
	char s[] = "abcde";
    
    permutation(s, 0, 4);
	return 0;
}

주의: 이 프로그램은 이렇습니다. abcde abced는 최내층의 귀속 함수입니다. abdce abdec abedc abecd는 꼴찌 2층의 귀속 함수입니다. 순서대로 유추합니다!사실은 for 순환과 귀속 함수의 삽입이다!주의해야 할 것은 이 함수는 문자열에 같은 문자가 없는 전체 배열 문제를 해결할 수 있을 뿐이다. 같은 문자가 있으면 중복되는 상황이 발생한다!!!