递归函数永远不会终止 [英] Recursive function never terminates
问题描述
我遇到了这个必须用递归解决的问题。
梯形游戏这个词是由Lewis Carroll在1877年发明的。这个想法是
以一个起始单词开头并一次更改一个字母，直到到达结尾单词
。沿途的每个单词都必须是英文单词。
例如，从FISH开始，您可以通过以下阶梯向MAST
创建一个单词阶梯：
FISH，WISH，WASH，MASH，MAST
编写一个程序，使用递归来查找单词ladder，给出一个开始
单词和结束单词，或者确定是否存在字梯。
我尝试过：
这是我的代码：
I was given this problem that must be solved using recursion.
The word ladder game was invented by Lewis Carroll in 1877. The idea is
to begin with a start word and change one letter at a time until arriving at
an end word. Each word along the way must be an English word.
For example, starting from FISH you can make a word ladder to MAST
through the following ladder:
FISH, WISH, WASH, MASH, MAST
Write a program that uses recursion to find the word ladder given a start
word and an end word, or determines if no word ladder exists.
What I have tried:
Here is my code:
#include<fstream>
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;
bool possible_bridge(string a, string b)//determine if a bridge can be formed between two strings
{
if (a.length()!=b.length())
{
return false;
}
bool difference=false;
for (int i=0;i<a.length();i++)
{
if ((a[i]!=b[i])&&(!difference))
{
difference=true;
}
else if ((a[i]!=b[i])&&(difference))
{
return false;
}
}
return true;
}
bool isRepeat(vector<string>& no_repeat,string word)//determine if there is already an indentical string in the vector
{
for (int i=0;i<no_repeat.size();i++)
{
if (no_repeat[i]==word)
{
return true;
}
}
return false;
}
void word_bridge(string last,vector<string>bridge[],bool& found,int size)
{
ifstream fin;
int count[size];
for (int i=0;i<size;i++)
{
count[i]=0;
}
for (int i=0;i<size;i++)
{
string word;
fin.open("text.dat");
while (fin>>word)
{
if ((possible_bridge(word,bridge[i][bridge[i].size()-1]))&&(!isRepeat(bridge[i],word)))
{
count[i]++;
}
}
fin.close();
}
int total=0;
for (int i=0;i<size;i++)
{
total+=count[i];
}
if (total==0)
{
cout<<"no ladder available\n";
return;
}
int n(0),i(0);
vector<string>temp[total];
for (int k=0;k<total;k++)
{
temp[k]=bridge[i];
n++;
if (n==count[i])
{
i++;
n=0;
}
}
n=0;
i=0;
string word;
fin.open("text.dat");
for (int k=0;k<total;k++)
{
do
{
fin>>word;
} while (!((possible_bridge(word,temp[k][temp[k].size()-1]))&&(!isRepeat(temp[k],word))));
temp[k].push_back(word);
n++;
if (n==count[i])
{
i++;
n=0;
fin.close();
fin.open("text.dat");
}
}
if (fin.is_open())
{
fin.close();
}
for (int i=0;i<total;i++)
{
if (temp[i][temp[i].size()-1]==last)
{
for (int k=0;k<temp[i].size();k++)
{
found=true;
cout<<temp[i][k]<<" ";
}
return;
}
}
if (!found)
{
word_bridge(last,temp,found,total);
}
}
int main()
{
vector<string>bridge[1];
bridge[0].push_back("ade");
bool found=false;
word_bridge("bqe",bridge,found,1);
}
我测试了这些功能，但它们运行良好除外用于word_bridge函数的递归部分。当我在递归部分之前添加一个简单的输出行cout<<123并运行程序时，程序输出123但没有终止或输出任何其他内容。
I have tested the functions and they work well except for the recursion part of the word_bridge function. When I added a simple output line cout<<"123" right before the recursive part and ran the program, the program output 123 but didn't terminate or output anything else.
推荐答案
开发分为四个部分：设计，代码，测试和调试。
你已经完成了前三个，现在是时候进行有趣的了：调试。
为什么不起作用？我不知道，因为你没有告诉我你怎么知道它没有 - 你没有告诉我你为了测试它做了什么，或者你得到了什么结果。这些很重要：他们告诉你，编码员，出了什么问题。
首先看看你做了什么：你输入了什么，以及发生了什么结果。任何错误消息都很重要。输出很重要。结果与您输入的内容和预期结果有何关系？当你有一个好的想法，是时候拿出调试器，并开始研究你为什么得到你的结果。
在线上设置断点
Development comes in four parts: Design, Code, Test, and Debug.
You've done the first three, and now it's time for the fun one: Debugging.
Why doesn't it work? I don't know, because you haven't told me how you know it doesn't - you haven't told me what you did in order to test it, or what results you got. And these are important: they tell you, the coder, what is wrong.
So start by looking at what you did: what did you enter, and what happened as a result. Any error messages are important. And output is important. How do the result relate to what you input and what you expected? When you've had a good think about about, it's time to bring out the debugger, and start working out why you get the results you do.
Put a breakpoint on the line
bridge[0].push_back("ade");并在调试器中运行您的应用。
当它到达断点时，它会停止，让你接管。您可以跨越行，逐步进入函数，查看（或更改）变量的内容。因此，请查看每一行，并确切了解运行时应该发生的事情。然后执行该行，看看发生了什么。这是你的期望吗？如果是这样，继续下一行。如果没有，为什么不呢？它做了什么？为什么它没有达到你的预期呢？
这是一项技能 - 在现实生活中也是一项非常有价值的技能 - 但开发它的唯一方法是使用它：你使用得越多越好！在这样的小程序上学习和开发技能要容易得多，而不是主要由不同的开发人员编写的100,000行庞然大物！
所以给它尝试一下，看看你能找到什么 - 它可能令人沮丧，但当你发现问题是什么时，这是开发中真正有趣的部分！
And run your app in the debugger.
When it hits the breakpoint, it will stop, and let you take over. You can step over lines, step into functions, and look at (or change) the content of variables. So look at each line, and work out exactly what should happen when it runs. Then execute the line, and look at what did happen. Is it what you expected? If so, continue for the next line. If not, why not? What did it do? Why didn't it do what you expected?
This is a skill - and a very valuable one in real life as well - but the only way to develop it is to use it: the more you use it the better you get! And it's a lot easier to learn and develop the skill on a little program like this, rather than a 100,000 line behemoth mostly written by a different developer!
So give it a try, and see what you can find out - it can be frustrating, but it's the real fun part of development when you find out what the problem is!
我同意OrifinalGriff，你应该学会尽快使用调试器。而不是猜测你的代码在做什么，现在是时候看到你的代码执行并确保它完成你期望的。
调试器允许你跟踪执行逐行检查变量，你会看到它有一个停止做你期望的点。
调试器 - 维基百科，免费的百科全书 [ ^ ]
掌握Visual Studio 2010中的调试 - A初学者指南 [ ^ ]
调试器在这里向您展示您的代码正在做什么，您的任务是与它应该做什么进行比较。 />
当代码不做ex的时候你接近一个bug。
你这里有一个错误：
I agree with OrifinalGriff, You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.
The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
When the code don't do what is expected, you are close to a bug.
You have a bug here:
int count[size];
for (int i=0;i<size;i++)>
{
count[i]=0;
}
如果在编译时已知 size ，则此代码可以正常工作。 br />
当 size 在运行时更改时，你需要一个指针，你必须手动分配和释放内存。
malloc - C ++参考 [ ^ ]
std :: malloc - cppreference.com [ ^ ]
这个错误是令人讨厌的，因为你的代码正在摧毁堆栈，每次你调用一个函数时，堆栈都会破坏你的变量。
This code works perfectly if size is known at compile time.
When size change at runtime, you need a pointer and you have to manually allocate and free memory.
malloc - C++ Reference[^]
std::malloc - cppreference.com[^]
This bug is nasty because your code is trashing the stack and every time you call a function, the stack is trashing your variable.
这篇关于递归函数永远不会终止的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
