5 replies to this topic

[Willum]

So, I'm following a book tutorial (C++ Without Fear, Second Edition) and one of the examples, is to better understand recursive functions is prime factorization. I understand the gist of it, I think, but whenever I run the program, it doesn't seem to work! Can anyone tell me what's going on?

#include <iostream>

#include <cmath>


using namespace std;


void get_divisors(int n);


int main(){


int n;


cout<<"Enter a number: ";

cin>>n;

get_divisors(n);

}


void get_divisors(int n){


int i;

double j = sqrt(n);


for(i=2; i<=j; i++){

    if (n % i == 0){

        cout<<i<<", ";

        get_divisors(n / i);

        return;

        }

    }

}

My only question about the program pertains to recursive functions, in general. When does the function end? Is it right before the 'recursive' part of the function ends? What I'm basically asking is this all that's executed:

int i;

double j = sqrt(n);


for(i=2; i<=j; i++){

    if (n % i == 0){

        cout<<i<<", ";

Thanks in advance!

[gregwarner]

Not sure I understand fully what your question is. I'll try to answer the best I can.

In its basic form, recursion looks like this:

RECURSIVE_FUNCTION (n):

  IF <base case>:

    RETURN c [where c is some discreet value]

  ELSE:

    RETURN RECURSIVE_FUNCTION(n') [where n' is some value computed from n, but differing from n]

  END IF.

END FUNCTION.

Each recursive function has a base case which causes it to terminate. This is where recursion ends. The function no longer calls itself, and that 'chain' of recursive calls comes to a close.

In the example above, concerning the return values, in the base case I have it returning 'c', which simply means a value in its own terms, not in terms of the recursive function. Since this is the base case, we cannot call itself again. However, in the recursive case (else), we must perform some modification on the input value to pass along to the next recursive call. The reason we must do this is because if we called the recursive function again using the same input, we would have an infinite loop. Whatever modification you perform to the input value brings it closer and closer to the base case, eventually causing the function to terminate.

In your example above, the halting condition (base case) is handled by this line:

for(i=2; i<=j; i++){

Eventually, the square root of the input will get so small (because you divide it in half with each recursive call) that it will be less than 2, causing the recursion to halt. However, that's not the only thing that will cause this function to halt. Suppose the input is 5. The for loop will run once, but fail the mod check, and so it won't recursively call itself on the first pass. Then, i increments, which causes the for loop to exit and terminate the function.

This also conveniently highlights where your code is broken for us as well: In the example above, the prime factorization of 5 should be: "5". However, your logic causes the function to terminate without printing anything.

Use 16 as your input and walk through the steps with pencil and paper to see how it works: You'll find the result of your above algorithm will be: "2, 2, 2", which is not the prime factorization of 16, but rather of 8.

In other words, you're missing the output of the final number in the series after recursion ceases. Hope that helps.

[lespauled]

For a recursion, I think a better example would be the classic reverse string example:

#include<iostream>

#include<string>

using namespace std;


void revDisplay(const string& a);


int main()

{

    string a;

    cout<<"Please enter a string"<<endl;

    getline(cin, a);

    revDisplay(a);

    return 0;

}

void revDisplay(const string& a)

{

    size_t n = a.size();

    if(n == 1)

        cout << a << endl;

    else

    {

        cout << a[n-1];

        string b = a.substr(0, n-1);

        revDisplay(b);

    }

}

the recursion key is :

size_t n = a.size();
if(n == 1)

if the key is hit, the recursion ends.

In the example above, if you put in (Super Bowl Reference): Giants

So the call stack will end up being:



revDisplay("Giants")
revDisplay("Giant")
revDisplay("Gian")
revDisplay("Gia")
revDisplay("Gi")
revDisplay("G") <= since the length is 1, recursion ends.

[Willum]

Thanks guys for the replies!

Gregwarner- I thought of that myself and inserted a cout command at the end of the function so it would display the end digit before I posted this thread, and it still didn't work! I suppose I may have put it in the wrong spot though. I believe I put it directly before the return; part of the function. Not sure if that's right, so I figured I'd ask, to make sure.

Lespauled- Thanks for the program, but I'm afraid it didn't help any... I get the basic jist of recursion, but unfortunatly I'm not too indepth with the C++ library, (I'm quite the beginner, I've only been learning c++ for about a month!) so I don't get many of the functions you've used. My main question is, where in the function does the function 'actually' end, which is what the recursion calls. That's all I'm confused about. I would like to get a more indepth knowlege of recursion is all.

Thanks again guys!

[lespauled]

In the main procedure, the only function that does any recursion is the revDisplay.

The revDisplay function is listed above.

Inside of revDisplay, the length of the string parameter is placed into variable n.

If n is 1, that means that the recursion is over, just print the last digit. <== ends here.

If n > 1, print out the last character, which is the size - 1. (a[n-1] );

Then create a new string, minus the last character that we just printed (string b = a.substr(0, n-1);)

Then call the same function (recursive) with the new string ( revDisplay(b);)

[gregwarner]

Willum said:

Gregwarner- I thought of that myself and inserted a cout command at the end of the function so it would display the end digit before I posted this thread, and it still didn't work! I suppose I may have put it in the wrong spot though. I believe I put it directly before the return; part of the function. Not sure if that's right, so I figured I'd ask, to make sure.

Post the revised code, as well as a specific description of how it's not working. (i.e., incorrect output, in which case, post examples)