Thread: 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);
    }
}

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.

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.

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 (:

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 !!