New to programming, help with recursive functions.

This is a discussion on New to programming, help with recursive functions. within the C Programming forums, part of the General Programming Boards category; Just started programming in C and I'm using SAMS Teach Yourself C in 21 Days (I'm not holding them do ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    2

    Unhappy New to programming, help with recursive functions.

    Just started programming in C and I'm using SAMS Teach Yourself C in 21 Days (I'm not holding them do that time frame though!)

    Anyway, chapter 5 is all about functions which are fine and I understand. However, they briefly mention recursive functions. Now I understand the theory, the function calling itself until a condition is reached but I just can't follow in me head their example. I'm nearly there but . . . ah!

    This is their code from an exercise question, can someone help me understand why the function doesn't return the value of 1 in every case?

    Code:
    #include <stdio.h>
    
    int three_powered( int power );
    
    main()
    {
    
    int a = 4;
    int b = 9;
    
    printf("\n3 to the power of %d is %d", a, three_powered(a));
    printf("\n3 to the power of %d is %d\n", b, three_powered(b));
    
    }
    
    int three_powered( int power )
    {
    
      if ( power < 1 )
        return ( 1 );
      else
        return( 3 * three_powered( power - 1 ));
    	
    }

  2. #2
    Registered User
    Join Date
    Jan 2007
    Location
    Euless, TX
    Posts
    144
    Well, look at the function and look at the parameter passed. If the passed parameter was 1, then it would return 1 immediately and quit. Let's say the parameter is 3, so the first part of the "if statement" is ignored and the "else" is executed. Then the next time, the function is "called" with a parameter of 2, and so on until the parameter is 1, and then the execution will stop and the value from the "recursion" is returned.

    Clear?

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    100
    Quote Originally Posted by HitchHiker View Post
    Just started programming in C and I'm using SAMS Teach Yourself C in 21 Days (I'm not holding them do that time frame though!)

    Anyway, chapter 5 is all about functions which are fine and I understand. However, they briefly mention recursive functions. Now I understand the theory, the function calling itself until a condition is reached but I just can't follow in me head their example. I'm nearly there but . . . ah!

    This is their code from an exercise question, can someone help me understand why the function doesn't return the value of 1 in every case?

    Code:
    #include <stdio.h>
    
    int three_powered( int power );
    
    main()
    {
    
    int a = 4;
    int b = 9;
    
    printf("\n3 to the power of %d is %d", a, three_powered(a));
    printf("\n3 to the power of %d is %d\n", b, three_powered(b));
    
    }
    
    int three_powered( int power )
    {
    
      if ( power < 1 )
        return ( 1 );
      else
        return( 3 * three_powered( power - 1 ));
    	
    }
    when you call three_powered(4):
    power<1? NO -- > return 3*three_powered(3);
    three_powered(3) --> return 3*three_powered(2);
    three_powered(2)--> return 3*three_powered(1);
    three_powered(1)-->return 3* three_powered(0);
    finally: three_powered(0) since 0<1 returns 1;

    NOW YOU GO BACKWARD:
    three_powered(0)-->returns 1;
    three_powered(1)-->rreturn 3*three_powered(0)=3*1=3
    three_powered(2)--> return 3*three_powered(1)= 3*3=9
    three_powered(3)-->return 3*three_powered(2)=3*9=27
    three_powered(4)-->return 3*three_powered(3)=3*27=81

    when you'll understand how the functions are called using the stack it will be easier to understand recursion.. bye!

  4. #4
    Registered User
    Join Date
    Sep 2008
    Posts
    2
    when you call three_powered(4):
    power<1? NO -- > return 3*three_powered(3);
    three_powered(3) --> return 3*three_powered(2);
    three_powered(2)--> return 3*three_powered(1);
    three_powered(1)-->return 3* three_powered(0);
    finally: three_powered(0) since 0<1 returns 1;
    This is as far as I got. Obviously it returns 1 at the end, couldn't work out how it could return any other value. I think I understand now, seems the book has forgotten to tell me about the stack. Maybe it will go into it later and things will click more.

    Thanks.

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by HitchHiker View Post
    This is as far as I got. Obviously it returns 1 at the end, couldn't work out how it could return any other value. I think I understand now, seems the book has forgotten to tell me about the stack. Maybe it will go into it later and things will click more.

    Thanks.
    But the value returned in the final step is returned to the previous level, where it is multiplied by 3, which is then returned to the previous level to that, where it is multiplied by 3 (giving nine), and so on, until the actual result is produced at the 4 levels back (81).

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    "can someone help me understand why the function doesn't return the value of 1 in every case?"

    This is a better question than at first I thought.

    Quote Originally Posted by kcpilot View Post
    If the passed parameter was 1, then it would return 1 immediately and quit. Let's say the parameter is 3, so the first part of the "if statement" is ignored and the "else" is executed. Then the next time, the function is "called" with a parameter of 2, and so on until the parameter is 1, and then the execution will stop and the value from the "recursion" is returned.
    In fact that's not true at all. For starters, "if the parameter passed was 1", it still recurses. Also, the execution does not "stop" because of this so that 'the value from the "recursion" is returned'. The return value is a series of mulitplications the final one of which is by one.

    If the power is one the return is three times 1. If power is two, the return is 3x3x1. If the power is three, the return is 3 x 3 x 3 x 1.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User
    Join Date
    Jan 2007
    Location
    Euless, TX
    Posts
    144

    Unhappy

    Mea Culpa --- old age is ruining my eyesight (and my ability to reason logically).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Loops or recursive functions?
    By mariano_donati in forum C Programming
    Replies: 5
    Last Post: 05-12-2008, 12:41 PM
  2. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 04:42 AM
  3. Passing pointers between functions
    By heygirls_uk in forum C Programming
    Replies: 5
    Last Post: 01-09-2004, 05:58 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21