分享
三行代码  ›  专栏  ›  技术社区  ›  leslie

递归函数显示分段问题C++

  •  0
  • leslie  · 技术社区  · 2 天前

    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    /**** Recursive backwards print, prints a string starting from last index to first*****/
    
    void printReverse(string s, int i)
    {
      if(i < s.size()) 
        {  
          printReverse(s.substr(1), i);
          cout<<s[i];
        }    
        else
        {   
          return;  
        }
      }
     
    
    
       /****   Recursive power function, computes a^b, where b can be positive or negative*****/
    int recPower(double a, int b)
      {   
        int i = b; //i = b, so int a can be multiplied int b times
         
        if (i == 0) //base 
          return 1;
    
        else //multiply A by B, B times
         {
           a *= b;
           return recPower(a, b); //recursive
           i--; //decrement i until it equals 0
         }
      }
    
    
       
       /****   Recursive string replace, replaces all instances of a character in a string with another character*****/
    string recReplace(string s2, int i, char old, char neW)
       { 
           if(s2[i] == old) //search for old char
          {
            i = neW; //replace it
            i++; //iterate i
           }
        recReplace(s2, i, old, neW); //call function
        return s2;
       }
    
    
    
    /****   Recursive list find   > Searches if x exists in list, returns true if found, false otherwise*****/
    int recListFind(vector<int> v, int i, int x)
      {
        if(v[i] == x)    
          {       
            cout << x << " exists in the vector."<<endl;  
            i++;
            recListFind(v, i, x);
          }    
          return true;
        }
    
    
    
    int main()
      {     
        cout << "PRINT REVERSE" << endl;
        cout << "----------" << endl;    
        string s1 = "hello world";    
        cout << "String: " << s1 << endl;    
        cout << "Reversed: ";    
        printReverse(s1, 0);       
        cout << endl;   
         
         
         /* Computes a^b (power function) */    
        cout << "POWER" << endl;    
        cout << "----------" << endl;    
        int a = 2, b = -3;    
        cout << a << "^" << b << " = ";    
        cout << recPower(a, b) << endl;    
        cout << endl;    
       
       
        /* Replaces a character in a string with a new one */    
        cout << "REPLACE" << endl;    
        cout << "----------" << endl;    
        string s2 = "-h-e-l-l-o-";    
        char oldChar = '-';    
        char newChar = ' ';   
        cout << "String: " << s2 << endl;    
        cout << "> Replace '" << oldChar << "' with '" << newChar << endl;    
        recReplace(s2, 0, oldChar, newChar);    
        cout << "String: " <<  s2 << endl;    
        cout << endl;    
       
       
        /* Searches for value in vector */    
        cout << "FIND" << endl;    
        cout << "----------" << endl;    
        int x = 7;    
        cout << "Does " << x << " exist in the vector? ";    vector<int> v = {5, 1, 6, 7, 9};    
        cout << recListFind(v, 0, 7) <<  endl;    
        cout << endl;    
      return 0;
    }
    
    1 回复  |  直到 2 天前
        1
  •  1
  •   Fantastic Mr Fox    2 天前

    问题是很直接的,你在做 recPower 函数 b . 在函数中,如果 b 不是0,你打电话 再供电 未修改的值为 b (不断修改 a ). 这总是以无限递归结束,这将使堆栈溢出。

    解决方案可以是:

    int recPower(double a, int b, int times) {        
      if (times == 0) 
        return a;
    
      else
        return b * recPower(a, b, --times); 
    }
    
    int recPower(double a, int b) {
        return recPower(a, b, b);
    }
    

    b 可以是负数,根据您的逻辑,它将在递减的同时继续递归,直到溢出并返回0。你将用你的第一个测试用例引起这个案例。您应该考虑这个函数中允许的类型,考虑使它们无符号,或者显式地处理负数 b 案例。