Đệ quy đuôi c++

#1

nhờ mọi người khai sáng não em , em chưa biết gì

#2

Chưa hiểu lắm là thế nào hả bạn.

Tức là hiểu một phần nhưng còn vướng mắc? Vậy bạn còn mắc chỗ nào?

Theo bạn thì thế nào là đệ quy, đệ quy đuôi là gì?

2 Likes
#3

ouch … câu hỏi quá mơ hồ khó trả lời :smiley:

3 Likes
#4

chắc là không bít gì luôn

#5

dạ chắc chưa biết gì luôn ạ

#6

Theo bạn thì thế nào là đệ quy, đệ quy đuôi là gì?

Vậy thì phiền bạn trả lời câu hỏi này của mình được không. :smiley:

Bạn có thể tự tìm tài liệu về đệ quy, lên wiki đọc cũng được, miễn sao là có câu trả lời cho mình. :smiley:

Còn chưa tìm hiểu gì mà đem lên hỏi mình cũng bó tay. :kissing:

3 Likes
#7

xin tài liệu ạ . em cũng có viết chương trình rồi mà , giống như kiểu đệ quy thường ,

#8

như này thì có đúng là đệ quy đuôi không ạ

#include<iostream>
#include<math.h>
using namespace std;
int tong(int n);
int main()
{
	int n;
	cout << "Nhap gia tri cho N = ";
	cin >> n;
	cout << "S = " << tong(n);
	return 0;
}
int tong(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return tong(n - 1) + n * n;
	}
}
#9

Đệ quy đuôi là một dạng trong đệ quy, đệ quy nói chung là ta có một hàm mà nó tự gọi lại chính nó. Giả sử @tuhoclaptrinh đã hiểu đệ quy là gì thì đệ quy đuôi chính là dạng hàm chỉ gọi chính nó rồi không làm gì khác nữa ,cũng là dạng mà mình thấy hay được dùng nhất.

Trong link này có giải thích + ví dụ https://cs.stackexchange.com/questions/6230/what-is-tail-recursion

3 Likes
#10

em cảm ơn, như này thì đúng không anh , em tự viết vài chương trình rồi mới lên hỏi , tại thấy nó giống với đệ quy thường

#include<iostream>
#include<math.h>
using namespace std;
int tong(int n);
int main()
{
	int n;
	cout << "Nhap gia tri cho N = ";
	cin >> n;
	cout << "S = " << tong(n);
	return 0;
}
int tong(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return tong(n - 1) + n * n;
	}
}
#11

^ cái này không phải là đệ quy đuôi bởi vì sau khi bạn gọi tong(n - 1) thì còn phải tính tiếp + n *n;

Đọc câu trả lời này https://cs.stackexchange.com/a/7869

Mình thử convert bài của bạn thành đệ quy đuôi thế này

#include<iostream>
#include<math.h>
using namespace std;
int tong(int n);
int main()
{
	for (auto i = 1; i <= 5; i ++) {
		cout << "N = " << i << ", ";
		cout << "S = " << tong(i) << endl;
	}
	return 0;
}

int tail_tong(int n, int result) {
	if (n > 1) {
		return tail_tong(n - 1, result + n * n);
	}
	return result;
}

int tong(int n)
{
	return tail_tong(n, 1);
}

Kết quả trả ra

N = 1, S = 1
N = 2, S = 5
N = 3, S = 14
N = 4, S = 30
N = 5, S = 55

Link tới editor mình dùng https://ideone.com/fgMlUG

Với code này thì compiler có thể dùng “jump” để thể hiện đệ quy thay vì phải dùng stack.

Compiler có thể thể hiện đoạn code này ở dưới dạng sau

int tail_tong(int n, int result) {
    start:
	if (n > 1) {
        result = result + n * n;
        n --;
        goto start;
	}
	return result;
}

Như thế này thì code sẽ được tối ưu hơn và không bị stackoverflow

5 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?