Thread: recursion

  1. #1
    Registered User
    Join Date
    Oct 2003
    Posts
    27

    recursion

    Can someone please explain recursive to me?! I know that recursion is a function calling itself, but when it says
    n = 4
    Code:
    int funt1 (int n)
    {
    if (n == 0)
    {
    return 1;
    }
    else
    {
    Return 2* funt1 (n-1);
    }
    I think thats right. Im doing it by memory.
    I am trying to write a program that takes a user input number and change the number into binary, octal, and the other one...lol. Its gotta have a class, a stack, and recursion.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    > I think thats right. Im doing it by memory.
    Well post what you actually tried then.
    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 Ephraim's Avatar
    Join Date
    Feb 2004
    Posts
    8
    first call:
    Code:
    funt1(4)
    Inside there:
    Code:
    funt1(4) calls -> funt1(4-1) calls -> funt1(3-1) calls -> funt1(2-1) calls -> funt1(1-1)
    now we are at the special point with n == 0 (remember your if(n == 0) )
    so the function returns a 1.
    and every time it returns it will be multiplied by 2.
    Code:
    funt1(4) -> funt1(4-1) -> funt1(3-1) -> funt1(2-1) -> funt1(1-1)
    16 <- 2*       <- 2*         <- 2*         <- 2*         <- 1
    so you will get 2^4 which is16.

    Hope it helped you

    Ciao Ephraim

  4. #4
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    ooh yay... another excuse to write a recursive function:
    Code:
    double power(int num,int exp);
    ...
    double power(int num, int exp)
    {
       if(exp==0)
          return 1;
       else if(exp>1)
          return (num*power(num,exp-1));
       else
          return num;
    }
    it goes all the way in, and when exp becomes 1, it returns num, which is multiplied by num and returned to the parent, which is multiplied by num and returned to the parent, which is...
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  5. #5
    Registered User Ephraim's Avatar
    Join Date
    Feb 2004
    Posts
    8
    Code:
    double power(int num, int exp)
    {
       if(exp==0)
          return 1;
       else if(exp>1)
          return (num*power(num,exp-1));
       else
          return num;
    }
    Tricky but for what reason do you have the
    if(exp == 0) there. You will never go into this section
    If Exp == 1 it not calls again the power but returns num.
    and so the exp isn't subtracted by -1, so never come into
    exp==0 section

    just kidding
    I like this way of programming, so the brain can get really f*****

    Ciao Ephraim
    Last edited by Ephraim; 03-03-2004 at 10:22 AM.

  6. #6
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    there's no trick there... what is X^0?

    this doesn' handle negative exponents well though...
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

  7. #7
    Registered User Ephraim's Avatar
    Join Date
    Feb 2004
    Posts
    8
    jep you are right
    Forgotten this point.
    and with the negative thing ...
    I think you can just use an unsigned int as exp isn't it?!

    Ciao Ephraim

  8. #8
    Registered User major_small's Avatar
    Join Date
    May 2003
    Posts
    2,787
    you could cast the exponent to an unsigned int, but what if they want to find out what x^-y is? they couldn't use this function (without modification) for it...
    Join is in our Unofficial Cprog IRC channel
    Server: irc.phoenixradio.org
    Channel: #Tech


    Team Cprog Folding@Home: Team #43476
    Download it Here
    Detailed Stats Here
    More Detailed Stats
    52 Members so far, are YOU a member?
    Current team score: 1223226 (ranked 374 of 45152)

    The CBoard team is doing better than 99.16% of the other teams
    Top 5 Members: Xterria(518175), pianorain(118517), Bennet(64957), JaWiB(55610), alphaoide(44374)

    Last Updated on: Wed, 30 Aug, 2006 @ 2:30 PM EDT

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM