귀속 사례

귀착의 난점은 귀착 깊이 있는 디자인과 그 중에서 논리 공식을 추출하는 데 있다.

하나.문자열 역방향

방법 1: 전역 변수를 수조로 표시합니다.

#define _CRT_SECURE_NO_WARNINGS
#include
#include

char dst[32];
static int i = 0;
void reverse_show(char *str)
{
	if (*str == 0)
		return;

	reverse_show(str + 1);
	dst[i++] = *str;
}

int main(int argc, char *argv[])
{
	char str[32] = "hello world";
	reverse_show(str);
	printf("%s
", dst);

	system("pause");
	return 0;
}

방법2: 문자열 복사 함수를 사용하여 되돌아오는 *str를 dst에 복사하여 역순을 실현한다.

void reverse_show(char *str)
{
	if (*str == 0)
		return;

	reverse_show(str + 1);
	dst[i++] = *str;

	// ， *str dst ， 。
	strncat(dst, str, 1);
}

둘.승계

논리 공식: 0!=1,n!= (n-1)!*n

int jie_cheng(int n)
{
	if (n == 0)
		return 1;

	return n*jie_cheng(n - 1);
}

셋.피보나치 수열

F(1)=1,F(2)=1, F(3)=2,F(n)=F(n-1)+F(n-2)(n>=4,n∈N*)

int fun(int n)
{
	if (n == 2 || n == 1)
		return 1;

	return fun(n - 1) + fun(n - 2);

}

넷.양의 정수를 역순으로 출력합니다.

위에서 문자열을 역순으로 출력하는 방법과 달리 문자열은++ 조작을 사용하는데 그 자체가 정렬이기 때문에 먼저 깊이 들어가고 나중에 출력해야 한다.수치에 대해서는 잉여 조작을 사용하고 역순으로 얻어지기 때문에 먼저 출력하고 나중에 잉여를 얻는다.

void fun(int n)
{
	printf("%d", n % 10);// 
	if (n >= 10)
		fun(n / 10);// 
}

오.한노타

fun(n) = 2*fun(n-1)+1;
해법 1:

int fun(int n) {
	if (n == 1) return 1;
	return 2 * fun(n - 1) + 1;
}

해법 2:

static int b = 0;
void hanoi_next(int n) {
	if (n > 0) {// 0， 。
		hanoi_next(n - 1);
		b++;
		hanoi_next(n - 1);
	}
}