Thread: Recursion

  1. #1
    Registered User
    Join Date
    Jan 2019
    Posts
    2

    Recursion

    Hello, my name is Igor and I'm a student. In the near future, we will have our exams, and I'm preparing for them right now. The issue I have is some of the problems that we have to practice are hard to solve, so I'm asking you to help me solve it.

    Recursion-capture-png

    This is the problem that I have to solve.

    This is my code:


    Code:
    double recursion(int n, int k)
    {
        if(n == 0)
            return ;
        if(k == 1)
            return sqrt(k/n+recursion(n--, k++));
        else
            return sqrt(k/n+recursion(n--, k--));
    }
    
    
    
    
    int main()
    {
        int n;
    
    
        scanf("%d", &n);
    
    
        printf("%f", recursion(n, 1));
    
    
        return 0;
    }
    I think I'm having a problem with the first part of my recursion function. I think I'm very close to solving it. Thanks for reading this and please help if you can!

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,763
    > return sqrt(k/n+recursion(n--, k++));
    Yeah, write it as
    return sqrt(k/n+recursion(n-1, k+1));

    Relying on the post-increment to actually pass a changed value to the recursive function will lead to weirdness.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User
    Join Date
    Jan 2019
    Posts
    2
    Quote Originally Posted by Salem View Post
    > return sqrt(k/n+recursion(n--, k++));
    Yeah, write it as
    return sqrt(k/n+recursion(n-1, k+1));

    Relying on the post-increment to actually pass a changed value to the recursive function will lead to weirdness.

    Nope, still not working.
    Code:
    double rekurzija(int n, int k){
        if(n == 0)
            return 0;
        if(k == 1)
            return sqrt(k/n+rekurzija(n-1, k+1));
        else
            return sqrt(k/n+rekurzija(n-1, k-1));
    }
    for n = 6, i get 1.010889, instead of 1.212149

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,763
    Perhaps you also need to do k/n in floating point, instead of as an integer (which it is at present).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User Kernelpanic's Avatar
    Join Date
    Sep 2018
    Location
    Berlin
    Posts
    103
    @Igor, I know that is not the right solution, and it is iterativ, but maybe a way there . . .
    It is an interesting task. - At until the solution: Take it easy!

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    
    int main(void)
    {
        double zaehler = 1.0, nenner = 6.0;
        double ergebnis, endsum = 0.0;
        
        for (int i = 1; i <= 6; i++)
        {
            ergebnis = sqrt(zaehler++ / nenner--);
            printf("\nErgebnis = %2.6lf\n", ergebnis);
            if (i % 2 == 0)
            {
                zaehler = 1.0;
            }    
            endsum += ergebnis;        
        }    
        printf("\nErgebnis = %2.6lf\n", endsum);
        
        return(0);
    }
    YouTube

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,560
    I would observe:
    • When the denominator is even, the numerator is 1; otherwise the numerator is 2.
    • The base case is when the denominator is 1. I suggest treating the case when the denominator is less than 1 as an input error.

    Clearly, you're currently not alternating the numerator between 1 and 2, so your code must be wrong, and your test result demonstrates that.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User Kernelpanic's Avatar
    Join Date
    Sep 2018
    Location
    Berlin
    Posts
    103
    @laserlight - He have to start from the end. - I will try it tomorrow.

    Have I say tomorrow? Today!

    6. 1,4142135623730950488016887242097
    5. 0,5
    = 1,9142 W: 1,3835461683659132594504455620589


    4. 2/3 = 0,66666666666666666666666666666667
    W aus 1,38 + 0,66 = 1,4318403076693527231520496645285


    3. 1/4 = 0,25 + 1,4318 = 1,6818
    W: 1,296842318865327589985079497541


    2. 2/5 = 0,4 + 1,2968 = 1,6968
    W: 1,3026127590347025308842363850784


    1. 1/6 = 0,16666666666666666666666666666667 + 1,3026 = 1,469266666666666
    W: 1,2121331060022519930524286807137
    1,2121...
    Last edited by Kernelpanic; 01-05-2019 at 05:58 PM.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,560
    Quote Originally Posted by Kernelpanic View Post
    @laserlight - He have to start from the end.
    What do you mean?

    EDIT:
    Meh, I just realised that the second "base case" isn't: rather, it is a complicated attempt to alternate between 1 and 2. Either compute or directly determine the numerator; don't repeat the entire expression.
    Last edited by laserlight; 01-05-2019 at 05:59 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User Kernelpanic's Avatar
    Join Date
    Sep 2018
    Location
    Berlin
    Posts
    103
    Quote Originally Posted by laserlight View Post
    What do you mean?
    See my correction - he have to start from the end.

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,560
    I don't see what your correction has to do with my post #6.

    EDIT:
    Anyway, in terms of correctness, I think the only thing missing now is changing the integer division to floating point. The base case being 0 is okay even though it doesn't strictly conform to the formula, and the complicated alternating between 1 and 2 is a readability issue rather than a correctness issue.
    Last edited by laserlight; 01-05-2019 at 06:10 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User Kernelpanic's Avatar
    Join Date
    Sep 2018
    Location
    Berlin
    Posts
    103
    Look that:
    Recursion-wurzelauswurzel-jpg


    He have to start from the end.
    That's a first try:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    
    int main(void)
    {
        double zaehler = 2.0, nenner = 1.0;
        double ergebnis, endsum = 0.0;
        double zwischen_sum;
        
        for (int i = 1; i <= 6; i++)
        {
            ergebnis = sqrt(zaehler-- / nenner++);
            printf("\nErgebnis = %2.6lf\n", ergebnis);
            if (i % 2 == 0)
            {
                zaehler = 1.0;
            }    
            zwischen_sum += ergebnis;
            //printf("\n%2d -- %2.6lf\n", i, ergebnis);
        }    
        printf("\nErgebnis = %2.6lf\n", endsum);
        
        return(0);
    }
    You understand?

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,560
    No, I don't. The recursion would begin with the denominator equal to the input, as per post #1's example. That isn't the "end"; I'd say that the base case is the "end", but of course after reaching the base case, control returns to the previous steps in the recursion in turn so as to finally return a result.

    Your "first try" is not recursive, so it is irrelevant, other than hinting that the recursive version is easily tail recursive. In fact, you can see the tail recursion in posts #1 and #3, although it is obscured by there being two return statements instead of one.
    Last edited by laserlight; 01-05-2019 at 06:36 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  13. #13
    Registered User Kernelpanic's Avatar
    Join Date
    Sep 2018
    Location
    Berlin
    Posts
    103
    I don't know whether the recursion ist part of the exerice but whether the solution is recursiv or iterativ the solution have to start from the last calculation.

    Recursion-wurzeliterativkomp-jpg

    I dont no whether this problem is resolvable iterativ. With "printf...":
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    
    int main(void)
    {
        double zaehler = 2.0, nenner = 1.0;
        double tmp, tmp2, tmp3, zsum;
        double endsum = 0.0;
        
        for (int i = 6; i >= 1; i--)
        {
            zsum = (zaehler-- / nenner++);
            
            if (i % 2 == 0)
            { zaehler = 1.0; }
            
            printf("\nzsum %2d -- %2.6lf", i, zsum);
            printf("\ntmp %2d -- %2.6lf", i, tmp);
            
            tmp = (zsum + tmp3);
            printf("\n%2c -- %2.6lf", 64 + i, tmp);
            
            tmp2 = sqrt(tmp);                
            printf("\ntmp2 %2d -- %2.6lf", i, tmp2);
            
            tmp3 = tmp2;                
            printf("\ntmp3 %2d -- %2.6lf\n", i, tmp3);
            zsum = 0;        
        }    
        printf("\nEndsumme = %2.6lf\n", endsum);
        
        return(0);
    }
    Without "printf()":
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    
    int main(void)
    {
        double zaehler = 2.0, nenner = 1.0;
        double tmp, tmp2, tmp3, zsum;
        double endsum = 0.0;
        
        for (int i = 6; i >= 1; i--)
        {
            zsum = (zaehler-- / nenner++);
            
            if (i % 2 == 0)
            { zaehler = 1.0; }
            
            tmp = (zsum + tmp3);        
            
            tmp2 = sqrt(tmp);                        
            
            tmp3 = tmp2;                        
            zsum = 0;        
        }    
        printf("\nEndsumme = %2.6lf\n", endsum);
        
        return(0);
    }
    Last output:

    Recursion-wurzel-ergebnis-jpg

  14. #14
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,560
    Quote Originally Posted by Kernelpanic
    whether the solution is recursiv or iterativ the solution have to start from the last calculation.
    You're mistaken, although I think you're just not phrasing it accurately. What you probably mean to say is that the computation of the formula can only be resolved after computing the in-most term (which appears to be what you mean by the "end" or the "last calculation"), and indeed the base case for recursion is part of the in-most term. You can see that the OP's recursive solution already does this.

    EDIT:
    For what it's worth, I checked that changing the integer division to floating point division in post #3 was all that was required to fix it, and it was. So I'd consider this solved, hence here's what I had in mind:
    Code:
    #include <stdio.h>
    #include <math.h>
    
    double compute(int n, int k)
    {
        double term = (double)k / n;
        if (n == 1)
        {
            return sqrt(term);
        }
        else
        {
            return sqrt(term + compute(n - 1, (k == 1) ? 2 : 1));
        }
    }
    
    int main(void)
    {
        int n;
        printf("Enter a positive integer: ");
        if (scanf("%d", &n) == 1 && n > 0)
        {
            printf("%f\n", compute(n, (n % 2 == 0) ? 1 : 2));
        }
        else
        {
            fprintf(stderr, "Error: invalid input\n");
        }
        return 0;
    }
    If the user enters the input of 6, you can see that compute(6, 1) is called, and the very first calculation (other than computing k) is that of 1.0/6, so it is not true that "the solution have to start from the last calculation". Yet, it is true that the solution must reach the base case where sqrt(2.0 / 1) is computed and returned, before the final result can be returned to main for printing.
    Last edited by laserlight; 01-07-2019 at 07:29 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  15. #15
    Registered User Kernelpanic's Avatar
    Join Date
    Sep 2018
    Location
    Berlin
    Posts
    103
    @laserlight - elegant solution! Clear and straight. Unfortunately not from me.
    The search for an iterative solution was nonsense.

    Thank you!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursion
    By arctic_blizzard in forum C Programming
    Replies: 9
    Last Post: 10-26-2008, 04:37 PM
  2. Recursion
    By trevordunstan in forum C Programming
    Replies: 5
    Last Post: 10-21-2008, 11:36 PM
  3. Recursion help please?
    By FusedOut in forum C Programming
    Replies: 4
    Last Post: 09-07-2003, 06:01 AM
  4. Recursion
    By Drew in forum C++ Programming
    Replies: 5
    Last Post: 08-21-2003, 06:20 PM
  5. Recursion
    By Peaches in forum C Programming
    Replies: 7
    Last Post: 11-22-2002, 09:09 AM

Tags for this Thread