Hàm đệ quy

Định nghĩa: Khi một hàm gọi tới chính nó người ta gọi đó là hàm đệ quy. Lý thuyết thì bao giờ cũng vu vơ trừu tượng bạn chạy các hàm sau và xem giải thích sẽ rõ hơn.

//UCLN tinh bang de qui

#include <stdio.h>
int UCLN(int a, int b)
{
	if(a == b)
		return a;
	else if(a>b)
		return UCLN(a-b, b);
	else
		return UCLN(a, b-a);
}
void main()
{
	int a,b;
	printf("
Nhap a: ");
	scanf("%d", &a);
	printf("
Nhap b: ");
	scanf("%d", &b);

	printf("
UCLN la: %d", UCLN(a,b));
}

Cho biết:

• f(n) = 0 khi n=0
• f(n) = 1 khi n=1
• f(n) = f(n-1) + f(n-2) khi n != 0, n!=1.

//fibo
#include <stdio.h>
int fibo(int n)
{
	if(n==0)
		return 0;
	else if(n==1)
		return 1;
	else
		return (fibo(n-1) + fibo(n-2));
}

void main()
{
	int n;
	printf("
Nhap n: ");
	scanf("%d", &n);

	printf("
fibo %d: %d",n,fibo(n));
}

Về cơ bản thì khi làm đệ qui thông thường sẽ có if và else và kèm theo một số dữ kiện nữa, cũng k bít nói sao túm lại là phân tích có dạng f(n) = f(n-1) + biểu thức.
ví dụ: f(n)=1/2 + 3/4 + 5/6 + … + (2n+1)/(2n+2).
Phân tích:

Nếu n = 0 thì f(n)=1/2
Nếu n !=0 thì f(n)=f(n-1)+(2n+1)/(2n+2).
Thế thì mình chỉ cần đệ quy nó lên là xong.

Kết luận:
Ok, vậy là có một chút ký ức về đệ quy rùi, làm một số bài sau đây sẽ hỉu rõ hơn nha pà kon: