Recursive function showing segmentation issue C++

Question

This code is for recursive function practice. When I run the code, it stops at the "POWER" cout line, then my compiler shows a segmentation error. The function that follows the POWER line is supposed to recursively raise number "a" to the power of number "b". I'm not sure how to fix this, can anyone help?

#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;
}

Fantastic Mr Fox · Accepted Answer · 2020-11-22 04:08:21Z

1

The issue is quite straight forward, you are doing the recPower function with b. In the function, if b is not 0, you call recPower with an unmodified value of b (whilst ever modifying a). This will always end up with infinite recursion which is going to overflow your stack.

A solution could be:

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);
}

Even if you fix this, you have another problem. b can be negative, which based on your logic will continue to recurse while decrementing until it overflows and goes back to 0. You will cause this case with your first test case. You should think about the types that are allowed in this function, consider making them unsigned, or dealing explicitly with the negative b case.

edited Nov 22, 2020 at 4:08

answered Nov 22, 2020 at 4:02

Fantastic Mr Fox

34.5k28 gold badges105 silver badges193 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Adrian Mole Over a year ago

Also for the recReplace function. From clang-cl: warning : all paths through this function will call itself [-Winfinite-recursion]

Fantastic Mr Fox Over a year ago

@AdrianMole Yeah, but the question is (or at least should be) only about the first one. I think the questions should remove the rest.

Collectives™ on Stack Overflow

Recursive function showing segmentation issue C++

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related