2

I'm attempting to write a function that recursively computes the resulting fibonacci number from a given int n using forks in C.

Here is the function specification: If doPrint is true, print it. Otherwise, provide it to the parent process. The solution should be recursive and it must fork a new child for each call. Each process should call doFib() exactly once. The method signature cannot be changed. Helper functions cannot be used.

This is a continuation of this question: Recursive Fibonacci using Fork (in C)

Unfortunately, I never figured out a solution to the problem in the last post, however this is my modified code. I thought I had it figured out (psuedo code wise) but came to find out that I still am unsure about a few pieces.

At this point, this is solely for my amusement. This is not homework and won't be covered in my class again (after the most recent test, which has passed).

static pid_t root_pid;

// Function to return exit code for PID
static int exitcode(pid_t pid)
{
    pid_t retpid;
    int status;

    retpid = waitpid(pid, &status, 0);
    if (pid != retpid)
    {
        printf("waitpid error\n");
    }

    return WEXITSTATUS(status);
}

static void doFib(int n, int doPrint)
{
    root_pid = getpid();

    pid_t pid1;
    int status1;

    pid_t pid2;
    int status2;

    if(n < 2) // Base case, exit back to parent?
    {
        exit(n);
    }
    else // if not base case, fork child processes
    {
        pid1 = fork();
        if (pid1 == 0) // Child Process 1 (for fib(n-1))
        {
            doFib(n-1, doPrint);
            exit(n-1);
        } 
        else if (pid1 > 0) // Parent Process
        {
            pid2 = fork();
            if (pid2 == 0) // Child Process 2 (for fib(n-2))
            {
                doFib(n-2, doPrint);
                exit(n-2);
            }

            // Get value from child process 1
            status1 = exitcode(pid1);
            // Get value from child process 2
            status2 = exitcode(pid2);

            // When to print?
            if (getpid() == root_pid)
            {
                int result =  status1 +  status2;
                if (doPrint)
                {
                    printf("%d\n", result);
                }
                else
                {
                    exit(result);
                }
            }
        }
    }
}

A few questions...

  1. Do I need to call both of these functions for each child process?

    doFib(n-1, doPrint); exit(n-1);
  2. Is my base case at the beginning correct? (n < 2)
  3. Is my base case at the end correct? (when to print)

Thank you for any help.

Improve this question
2
  • 1
    As you explore this coding problem, you should consider that a recursive solution to the Fibonacci problem is a pretty bad way to get a result, as it's horribly inefficient. Commented Feb 16, 2012 at 15:03
  • @Pointy Appreciate the two cents. It was from a set of coding problems I was completing to prepare for a midterm, and I never figured this one out. It's been bothering me to say the least, but I'm sure it's for educational purposes mostly. Commented Feb 16, 2012 at 16:37

1 Answer 1

Reset to default
1

The answer for "when to print" really comes down to what you want to print ... if you only want to print the final answer, then you'll most likely need a flag that indicates when you're in the root parent process, and use the if statement to test if you are indeed the root parent so that you only print a single number. If on the other-hand you want to print the entire sequence up to the final number, then an if statement is not needed.

For instance, a good flag value would be the PID of the root process. You could save this in a global variable called root_pid in the first couple lines of main() before you start your forking off of separate child processes. That way all the child processes will have the same value set for root_pid, and the if statement can simply be if (getpid() == root_pid).

So do something like this:

//fib.c
#include <unistd.h>
pid_t root_pid

int main()
{
    root_pid = getpid();

    //... rest of your program

}

And as mentioned above, make your if statement inside of doFib the following:

if (getpid() == root_pid)
{
    //...print results
}
else
{
    exit(result)
}
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

The final answer is what I'd need to print, not the sequence. I had thought I might need to detect if I'm the root parent for the end base case condition. Could you provide some code examples on how to detect if the current pid is the root/top process? I googled it to no avail.
Thanks, this looks like a good solution to the end base case. Very much appreciated. Now hopefully someone can figure out the rest. ;)
BTW, those exit(n-1) lines in your if statements for the children are dangerous, and will lead to erronious results if they are ever called. You need to make sure that either you call the first exit(n) in your base-case, or your code calls exit(result) ... it can't do anything else if you want correct answers. Another option would be doFib returning the result value, and then calling exit(result) after doFib(). But you can't have a separate exit() path from the proper recursive exit points without incurring erroneous results.
I see, thanks for the additional input. Every time I've tried to take them out it's resulted in an infinite loop, which I assume is because my base cases were incorrect. Now I'm getting several "waitpid" errors when I remove them. Huff...
That's because you've embedded the exit(result) inside another nested if statement, so it's not called if the process is not the root PID ... it needs to be the option if the current PID is not the root-process PID.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.