c++ - 如何停止递归？

Question

下面的代码是在树中找到加起来等于给定总和的路径...我在这里所做的是排队所有节点的值到一个数组 path 并在条件满足时递归打印....

void checkSum(NODE* root, int path[], int len, int sum){

     if(root == NULL) return;

     path[len] = root->data;
     len++;

     if(sum - root->data == 0){ 
            sum -= root->data;
            cout<<"\nSum equals..."; 
            printPaths(path, len); 
     }
     else if(sum - root->data > 0){
          sum -= root->data;
          checkSum(root->left, path, len, sum);    
          checkSum(root->right, path, len, sum);
     }else { return; }
}

我想知道的是，有没有其他方法可以在不使用任何数据结构的情况下打印路径(至少一个)？？？

像这样的....

void checkSum_second(NODE* root, int sum){

     if(root == NULL) return;

     if(sum - root->data == 0) {  
          //do something
     }     
     else if(sum - root->data > 0){
          sum -= root->data;                 
     }else return;


     checkSum_second(root->left, sum);
     checkSum_second(root->right, sum);     
     cout<<"\nvalue..."<<root->data;
}

考虑一棵树

           1
       2       3
    4    5   6   7

如果 sum = 7 checkSum_second(root->left, sum); 被执行三次，即，直到节点 4，在这里我们是否可以停止一切，只是打印堆栈(即清空它)......

Answer 1

要尽早终止递归，您需要在调用链上传递某种信号。在您的情况下，您可以将返回类型更改为 bool，并返回 true 以指示搜索已终止，不需要进一步处理:

bool checkSum(NODE* root, int path[], int len, int sum) {
     if(root == NULL) return false;
     path[len] = root->data;
     len++;
     if (sum - root->data == 0){ 
          sum -= root->data;
          cout<<"\nSum equals..."; 
          printPaths(path, len);
          return true;
     } else if (sum - root->data > 0) {
          sum -= root->data;
          if (checkSum(root->left, path, len, sum)) {
              return true;
          }
          if (checkSum(root->right, path, len, sum)) {
              return true;
          }
     }
     return false;
}

请注意，在上面的代码中，递归调用仅在先前的调用继续返回 false 时才会继续。从调用返回的第一个 true 被发送到调用链，导致整个调用链终止。