Thread: Recursive function confusion

  1. #1
    Registered User
    Join Date
    Jul 2004
    Posts
    30

    Recursive function confusion

    Greetings. I'm just starting programming in C and I'm stuck on the logic of a simple recursive function. I'm working with a function that calculates the value of 3 raised to the nth power. My solution was:

    Code:
    int result = 3;
    
    long power(int exponent)	
    {
    if(exponent<1)
    return 1;
    else
    result *= 3;
    power(exponent-1);
    return result;
    }
    This worked fine. However, according to the book that I'm learning from, the solution is written more compactly as:

    Code:
    long power(int exponent)
    {
    if(exponent<1)
    return 1;
    else
    return (3 * power(exponent-1));
    }
    I don't understand how the two are equivalent. In other words, how exactly does "(3 * power(exponent-1))" work? It seems to me that "power(exponent-1)" must evaluate to the product of 3 multiplied by itself (exponent-1) times, but how is this calculation accomplished? Where does the 3*3*3... actually happen?

    Thanks for your help!

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Well with your solution it does not work as you are never assigning the return value to anything nor using it right away.

    Their solution works by immediatly using the return value of power().

    So say you want to find 3 to the power of 3. So you make the call power(3)
    It goes into the function does the condition, 3 < 1 is false so it goes to the else condition.
    It goes I'm going to return the value of 3 times whatever the return value of power(2) is

    So it goes into power(2) so it can get the return value, which in turn makes a call to power(1) which in turn makes a call to power(0). Finally it stops and you are left with:
    (3 * (3 * (3 * (1) ) ) ) and then it starts working from the inside out and does the multiplication and gets 9, which the very first call to power() returns.

  3. #3
    Registered User
    Join Date
    Jun 2004
    Posts
    277
    Quote Originally Posted by Sereby
    Greetings. I'm just starting programming in C and I'm stuck on the logic of a simple recursive function. I'm working with a function that calculates the value of 3 raised to the nth power. My solution was:

    Code:
    int result = 3;
    
    long power(int exponent)	
    {
    if(exponent<1)
    return 1;
    else
    result *= 3;
    power(exponent-1);
    return result;
    }
    This worked fine. However, according to the book that I'm learning from, the solution is written more compactly as:

    long power(int exponent)
    {
    if(exponent<1)
    return 1;
    else
    return (3 * power(exponent-1));
    }
    I don't understand how the two are equivalent. In other words, how exactly does "(3 * power(exponent-1))" work? It seems to me that "power(exponent-1)" must evaluate to the product of 3 multiplied by itself (exponent-1) times, but how is this calculation accomplished? Where does the 3*3*3... actually happen?

    Thanks for your help!

    when tou call power(exponent-1) you are saying to the PC, okay call the power function again, but with another value, in this case exponent-1

    Imagine you have 3³, here we go:

    Code:
    long power(int exponent)// exponent here is 3
    {
    if(exponent<1) // exponent is > than 1 so we keeo going
    return 1;
    else
    return (3 * power(exponent-1));/*NOW PAY ATTENTION! here we have 3*3² and                     
     we will return it calling power again,  what you should be able to see is that this calling will make the function run again but you will be returning 3¹ as power-1 it is like first loop I have 3³ wich is 3*3² second loop 9*3¹ so the 3*3 happens each time the function is called again!*/
                                                                        
    }

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Well if you are using an integer return type then any negitive exponent wouldn't be correct as all negitive exponents would yeild a result 1<x<0 (unless of course the base was negitive but lets keep it simple )

  5. #5
    Registered User
    Join Date
    Sep 2001
    Posts
    4,912
    Which I realized before deleting my post. Thanks Thantos

  6. #6
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    @Maragato: In the future when using code tags please keep the comments short as to avoid the uglyness of the horizontal scroll

  7. #7
    Registered User
    Join Date
    Jul 2004
    Posts
    30
    Ah hah! Now I understand. Thantos & Maragato, your illustrations were very clear! Many, many thanks, all.
    Last edited by Sereby; 07-22-2004 at 12:48 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 05:42 AM
  2. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  3. recursive function
    By tonderai76 in forum C++ Programming
    Replies: 11
    Last Post: 04-21-2004, 12:49 PM
  4. Replies: 5
    Last Post: 02-08-2003, 07:42 PM
  5. structure vs class
    By sana in forum C++ Programming
    Replies: 13
    Last Post: 12-02-2002, 07:18 AM