Thread: understanding recursive functions

  1. #1
    Registered User
    Join Date
    Dec 2004
    Posts
    10

    understanding recursive functions

    Hi, this is my first post here.

    I'm having trouble understanding the logic of recursive functions. I'm doing a self study on C programming for linux and I'm having problems understanding how recursive functions work.

    like I have no idea what's going on here, and the book doesn't further explain recursive functions to enlighten me: What's going on here?

    Code:
    /* Takes the value 3 to the power of another number */
    
    #include <stdio.h>
    
    int three_powered (int power);
    
    int main(void)
    {
        int a = 4, b = 19;
    
        printf("3 to the power of %d is %d\n", a, three_powered(a));
        printf("3 to the power of %d is %d\n", b, three_powered(b));
    
        return 0;
    }
    
    int three_powered (int power)
    {
        if (power < 1)
            return 1;
        else
            return 3 * three_powered (power -1);
    }
    I'm just not understanding it. Any help is appreciated. I really want to understand this.

    Psuedo code might help me to understand it.
    Last edited by houler; 12-09-2004 at 10:09 AM.

  2. #2
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,212
    http://www.legcramp.co.uk/diagram.gif

    recursive functions are difficult to understand at first, as people tend to think of functions as a machine, that take an input and produce a result. Functions are like steps in achieving a result, and if a result requires that step to be repeated, the function can call itself in what is called recursion.

    Don't worry, you'll get it as soon as someone comes along and explains it better than I can.

    Try writing a function that uses recursion to add all the numbers less than a number together.

    for instance if you called function(7)
    it would return the result to this:
    7 + 6 + 5 + 4 + 3 + 2 + 1
    Last edited by Brian; 12-09-2004 at 10:14 AM.

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    Recursive functions call themselves. If they were to do so without any type of check, they would quickly eat up memory resources and crash your program. This check in the sample provided is done by the following if test:

    Code:
    if (power < 1)
        return 1;
    As long as our power variable is more than 1 we will keep skipping this return statement and execute the else part which is the part that calls itself.

    Code:
    else
        return 3 * three_powered (power -1);
    You will notice that in the recursive call, we call the function again but this time we reduce the value of the argument provided to the function by 1. This argument happens to be what the function tests against to check whether it is time to stop calling itself. This ensures that eventually we will end up calling the function with an argument that will satisfy the if portion of the test which breaks the recursion. All recursive functions must in some way modify whatever value is tested as the "stop" condition so that we reach that stopping point.

    So, lets say we call the function initially with a value of 4:

    Code:
    three_powered(4)
    Is 4 less than 1?  No...
    Return 3 * three_powered(3)
               Is 3 less than 1? No...
               Return 3 * three_powered(2)
                          Is 2 less than 1? No...
                          Return 3 * three_powered(1)
                                     Is 1 less than 1? No...
                                     Return 3 * three_powered(0)
                                                Is 0 less than 1? Yes...
                                                Return 1;
    From the above we can now work backwards towards our answer.

    Code:
    three_powered(0) returns 1.
    three_powered(1) returns 3 * three_powered(0) = 3 * 1 = 3.
    three_powered(2) returns 3 * three_powered(1) = 3 * 3 = 9.
    three_powered(3) returns 3 * three_powered(2) = 3 * 9 = 27.
    three_powered(4) returns 3 * three_powered(3) = 3 * 27 = 81.
    So, we get our final answer of 81 which is 3 raised to the 4th power.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    Just run through it in your head.

    You start off in main(). You call three_powered() and pass 4 to it. Now you're inside three_powered() and you check if 4 is less than 1. it's not so you go to return 3 * three_powered ( power -1) (odd spacing...but that's irrelevant). Before you can return to main() though, you need to evaluate the return value. So you call three_powered() again and pass 3 to it (4 - 1). The process goes again and you end up calling it again with the value 2, and then with the value 1, and finally with the value 0. This whole time, your function calls have been building up on the stack so they look like this:

    main()
    three_powered()
    three_powered()
    three_powered()
    three_powered()
    three_powered() <-- you are here

    power is less than 1 this time so you return 1 to the calling function. Now that one returns 3 * 1 to its calling function. That one returns 3 * 3 to its calling function. That one returns 3 * 9 to its calling function. And finally, that one returns 3 * 27 to its calling function which is main(). Then the printf() can be called and it shows that 3 to the power of 4 is 81.

    The second printf() doesn't have enough parameters passed to it.
    If you understand what you're doing, you're not learning anything.

  5. #5
    Registered User
    Join Date
    Dec 2004
    Posts
    10
    I get it now, thank you for your quick replies.

  6. #6
    Registered User
    Join Date
    Dec 2004
    Posts
    10
    Quote Originally Posted by Brian
    http://www.legcramp.co.uk/diagram.gif

    recursive functions are difficult to understand at first, as people tend to think of functions as a machine, that take an input and produce a result. Functions are like steps in achieving a result, and if a result requires that step to be repeated, the function can call itself in what is called recursion.

    Don't worry, you'll get it as soon as someone comes along and explains it better than I can.

    Try writing a function that uses recursion to add all the numbers less than a number together.

    for instance if you called function(7)
    it would return the result to this:
    7 + 6 + 5 + 4 + 3 + 2 + 1
    Code:
    /* Demonstrates a recursive function */
    
    #include <stdio.h>
    
    int recurse(int a);
    
    int main(void)
    {
        int num;
    
        printf("Enter a number: ");
        scanf("%d", &num);
    
        printf("= %d\n",  recurse(num));
    
        return 0;
    }
    
    int recurse(int a)
    {
        if (a < 1)
            return 0;
        else
        {
             if(a == 1)
                 printf("%d ", a);
             else 
                 printf("%d + ", a);
             
             return a += recurse(a - 1);
        }
    }
    How's that Brian?
    Last edited by houler; 12-09-2004 at 12:43 PM.

  7. #7
    Registered User
    Join Date
    Dec 2004
    Posts
    10
    nevermind.
    Last edited by houler; 12-09-2004 at 11:59 AM.

  8. #8
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,212
    Good job

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Question about Recursive Functions
    By jack999 in forum C++ Programming
    Replies: 5
    Last Post: 05-15-2006, 05:14 PM
  2. Passing pointers between functions
    By heygirls_uk in forum C Programming
    Replies: 5
    Last Post: 01-09-2004, 06:58 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. writing functions
    By jlmac2001 in forum C++ Programming
    Replies: 5
    Last Post: 09-20-2003, 12:06 AM
  5. need help with recursive functions
    By datainjector in forum C Programming
    Replies: 3
    Last Post: 07-18-2002, 07:32 PM