Recursive Functions

This is a discussion on Recursive Functions within the C Programming forums, part of the General Programming Boards category; I am not understanding recursive functions, especially when called in a compound statement here's a sample program with void function. ...

  1. #1
    Unregistered
    Guest

    Recursive Functions

    I am not understanding recursive functions, especially when called in a compound statement


    here's a sample program with void function.
    I don't know what the function does.
    I am getting a segFault and don't know why.
    And I need to get a full understanding of the recursive function.
    HOW DOES THE LINE AFTER THE CALL IN THE FUNCTION GET USED IF THE FUNCTION KEEPS CALLING ITSELF??? Basically how does anything get printed if the function continuously callss itself.

    Someone told me that the call goes forward until the != 0 is false, then the function 'unwinds' and that is when it calls itself in reverse and the putchar function is then acted upon.
    Is this true????? I don't get that. Please explain.



    Code:
    #include <stdio.h>
    
    void func(int n);
    
    main()
    {
       int q=0;
       printf("Enter a number:  ");
       scanf("%d",q);
    
       func(q);
    }
    
    void func(int n)
    
    {
        if (n != 0)   {
          func(n / 2);
          putchar ('0' + n % 2);
        }
    }

  2. #2
    Banned Troll_King's Avatar
    Join Date
    Oct 2001
    Posts
    1,784
    You didn't use scanf properly. You need to put an ampersand '&' in there. Also the main function should be preceded by and int return type and the main function should always return 0, signifying sucessful completion.

  3. #3
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    You have to use return statements to make recursive functions make a lick of sense.
    Code:
    void func(int n)
    {
        if (n != 0)   {
          func(n / 2);
          putchar ('0' + n % 2);
        }
        return;
    }
    Now let's suppose that we are going to call func(5)...

    1. Call func(5). We now enter the 1st instance of func.
    2. Check (5 != 0)? TRUE
    3. Therefore call func(2). We now enter the 2nd instance of func.
    4. Check (2 != 0)? TRUE
    5. Therefore call func(1). We now enter the 3rd instance of func.
    6. Check (1 != 0)? TRUE
    7. Therefore call func(0). We now enter the 4th instance of func.
    8. Check (0 != 0)? FALSE
    9. Therefore we skip the body of the if, and return to caller, terminating the 4th instance of func.
    10. The caller was the 3rd instance of func, the command after func (1) is purchar ('0' + 1 % 2), so we putchar ('1').
    11. Next command is return to caller, terminating the 3rd instance.
    12. The caller was the 2nd instance of func, the command after func (2) is purchar ('0' + 2 % 2), so we putchar ('0').
    13. Next command is return to caller, terminating the 2nd instance.
    14. The caller was the 1st instance of func, the command after func (5) is purchar ('0' + 5 % 2), so we putchar ('1').
    15. Next command is return to caller, terminating the 1st instance.

    Now, looking at all the observable actions which we've done, we've printed "101" (10, 12, and 14).

    func will not call itself forever because eventually it is going to have to call func(0), and when it does that, it returns without calling itself.

    Also, there's an error in your code, which is causing the fault
    Code:
    scanf("%d",q); // ??
    // scanf ("%d", &q);
    As a final point, I'd like to say that this is a frighteningly confusing example of a recursive function.

  4. #4
    Ian
    Ian is offline
    Registered User
    Join Date
    Oct 2001
    Posts
    21

    Troll found the problem

    If you add the '&' as Troll suggests that gets rid of the segmentation fault.

    Example: scanf("%d",&q);

    I don't really know how to explain what your function is doing. It is calling itself again and again until n is 0.(Like your friend said) Namely if I put in 5 for my number it would put 5 in the first time, and then since 5 is not 0 it would call func(5 / 2) which = 2, (it rounds down because you are using an int data type rather than a float) it then checks to see if 2==0, it does not, so it alls func(2/2) which is 1, does 1==0? nope, so it calls func(1/0) (which is 0 because we round down) then it is 0 so it prints 'n%2' modulus is the remainder when it is divided, then it escapes that function and goes back to the previous and prints what 'n%2' is in that function, (n is 1 in that function) then it goes to the previous function (where n was 2 and prints 'n%2' again, and so on and so forth....

    The short version: it converts a decimal based number that you enter into binary

    I imagined I just confused more than helped... but oh well (:
    The typing practice was worth it right? ..... right?
    Ian (:

  5. #5
    Unregistered
    Guest

    Thumbs up Thanks

    Actually, QuestionC helped immensely, as far as figuring out the order of thinking that the program goes through to do the calls then print using putchar.

    And duh, forgetting the & in the scanf is a typically newbie error.

    And when I did change my scanf statement to proper coding, it worked. And I get the decimal to binary, thanks, Ian. (my nephew's name is Ian, how about that ????)



    Thanks y'all !!

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, 01:41 PM
  2. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 05:42 AM
  3. Passing pointers between functions
    By heygirls_uk in forum C Programming
    Replies: 5
    Last Post: 01-09-2004, 06:58 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10: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, 09:15 AM

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