How do I write a loop function as a recursive function?

Question

Well, I've been trying to rework this many times. Though, at one point I thought the longestSequence function would help, since it displays the longest hailstone sequence. Though, I can't seem to figure out how to find, or store the value it used to find that.If someone could explain how, I would appreciate it.

int longestSequence(int n)
{
    int u = n;

    if(u == 1)
    {
        return 1;
    }
    else 
    {
        return max(hailstoneLength(u), longestSequence(u-1));
    }
}

The part I'm having trouble with is my longest start sequence:

int hailLongestSeq(int n)
{
    int k;
    int longest = 0;
    for(int j = 1; j <= n; j++)
    {
        if(hailstoneLength(j) > longest)
        {
            longest = hailstoneLength(j);
            k = j;
        }
    }
    return k;   
}

I'm not sure how to make this into a recursion, I noticed for some recursions I saw people using for loops still, but I was sure we weren't supposed to use loops. It may be a dumb question, but is there a formula to translating for loops to recursions, if anyone knows one?

The expected out put is like this:

The longest hailstone sequence starting with a number up to 10 has length 20. The longest hailstone sequence starting with a number up to 10 begins with 9.

as 9's sequence has a length of 20 numbers, and is the longest from 1 to 10.

the formula is reword the problem in terms of sub problems: example: a for loop of n iterations is an iteration over a for loop of n-1 iterations — perreal
– perreal, Commented Sep 23, 2016 at 5:02
No I didn't ask this yesterday. I submitted this at 1 am today — Zabe
– Zabe, Commented Sep 23, 2016 at 18:13

Jean-Baptiste Yunès · Accepted Answer · 2016-09-23 05:13:45Z

4

Yes every for loop can be translated to recursive call, obviously like this:

for (i=0; i<N; i++) {
  body;
}

translate it to:

func(int i) {
  if (i<N) { body; func(i+1) }
  else return;
}

func(0);

This can be easily extended to any for loop computation (add parameters if needed, return value, etc).

edited Sep 23, 2016 at 5:13

answered Sep 23, 2016 at 5:02

Jean-Baptiste Yunès

36.6k4 gold badges51 silver badges76 bronze badges

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

2 Comments

Zabe Over a year ago

Wow. Thanks! I'm still learning C++. I should probably save this in case I need it again.

Zabe Over a year ago

When i do this I'm gettign a segmentation fault. How do I fix that? or am I doign anythign wrog?

Rishabh Kumar · Accepted Answer · 2016-09-23 19:39:14Z

0

You can add the local variables who's value you want to retain in the parameter signature of the function. I have tried to rewrite the code as recursive. Check and verify if this solves your problem.

int hailLongestSeq(int n, int j, int k, int longest)
{
    if(j <= n)
    {
        if(hailstoneLength(j) > longest)
        {
            longest = hailstoneLength(j);
            k = j;
        }
        k = hailLongestSeq(n, ++j, k, longest);
    }
    return k;   
}

This may need a fix, however the logic remains the same, pass the variables as parameter to retain the value.

edited Sep 23, 2016 at 19:39

answered Sep 23, 2016 at 5:13

Rishabh Kumar

5575 silver badges15 bronze badges

5 Comments

Zabe Over a year ago

Same with this, I'm gettign a segmentation fault

Rishabh Kumar Over a year ago

Sorry I acidentally added j++ instead of ++j that was resulting in infinite loop. I have modified the code now. Can you check again and confirm if it is working for you.

Zabe Over a year ago

Oh yes, it works Rishabh, thanks. Thanks, and if it's alright, is it alright if I can get an explanation on how this works? I'm working through more hand simulations.

Rishabh Kumar Over a year ago

Well honestly, I just converted your loop logic to recursion. First thing to convert loop is to create a condition based on your loop condition. If the condition is satisfied then call the function again, else return the output. Also make sure that all the local variables used in the function are passed as parameter while making a recursive call. For complex tasks I always find it better to write loops first and then convert it to recursive functions. Keep practising. Please upvote if you got the point.

Zabe Over a year ago

I understand that pretty well now, Though sorry, I can't upvote as i dont have 15 rep, but I noticed it was also explained above. When i followed their way it resulted the same. Thanks again.

Collectives™ on Stack Overflow

How do I write a loop function as a recursive function?

2 Answers 2

2 Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related