Results 1 to 2 of 2

Math Help - calculation of recursion

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    1

    calculation of recursion

    How often will occur * ?

    void Star(int n) {
    for (i=0;i<n;i++) {
    printf("*");
    Star(i);
    }
    }


    I thing so 2^n - 1, but I don`t know how I can count it.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785

    Re: calculation of recursion

    You are right about the number of *. Let's call the number of * printed by a call to Star(n) by s_n. The program gives rise to the recurrence relation on s_n:

    s_n=\sum_{i=0}^{n-1}(1+s_i)=n+\sum_{i=0}^{n-1}s_i.

    After you have a recurrence relation, you can calculate the first several values and make a hypothesis about the general formula, but you have already done this. Then you need to prove this hypothesis, i.e., s_n=2^n-1 for all n, by induction on n using the recurrence relation.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recursion help.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 28th 2010, 03:23 PM
  2. recursion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 13th 2009, 08:00 AM
  3. Recursion problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 21st 2008, 07:11 AM
  4. Recursion
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 30th 2008, 10:40 PM
  5. Recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 16th 2008, 07:24 PM

Search Tags


/mathhelpforum @mathhelpforum