Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to parts to my questions and I am a beginner at programming. Im not sure how to translate a code into a diagram.

Draw a diagram illustrating the values as the function is called… and the values as each call is retuned….

  • Write a non recursive version of this function… using a regular loop.
share|improve this question
    
Would you mind posting the function you are talking about? –  Kenny Hegeland Jul 29 '13 at 4:38
    
A function call is "buffered" on the system stack. A general method to eliminate recursive calls is to create your own stack. However, this generally is not what most exercises want you to do. I believe what is wanted depends on the problem. For example, computing the $n$-th Fibonacci number requires knowing only the $(n-1)$-th and $(n-2)$-th, and the extra amount of memory needed is only $O(1)$. –  Tunococ Jul 29 '13 at 4:40
    
I think Im suppose to make up my own function –  kcamp Jul 29 '13 at 4:44
    
Actually this was an example posted before the question so it might be related.Example 1 void myFunction( int counter) { if(counter == 0) return; // if base case condition is true, then stops, and returns.. else { // if base case condition is greater then zero, call it self again cout <<counter<<endl; myFunction(--counter); return; } } int main() { int x = 10; myFunction(x); //call function } –  kcamp Jul 29 '13 at 4:45
    
The idea of diagramming the problem is to give you an idea of what the function does at each step, after doing this it should be easier to write the function non recursively. For example, if x=3, what happens on the first pass through the function? The second? –  Kenny Hegeland Jul 29 '13 at 4:55

1 Answer 1

Here is an example of a function which is different from the one you provided, however I feel it will allow you to solve your problem.

Let us consider the factorial function, which can be defined as follows:

$$ n!=\begin{cases} 1 & \textrm{ if $n=0$}\\ n(n-1)! & \textrm{ otherwise }\\ \end{cases}. $$

This is actually a recursive definition of the factorial function. Some quick c code will look something like this

int factorial(int m){
    if(m == 0){
        return 1;
    }
    return m*factorial(--m);
}

Now what happens if we run factorial(3) ?

Originally we have $m=3$ and so we skip the if clause and we return 3*factorial(2). Running factorial(2) will give us return 2*factorial(1), now we run factorial(1) and we get return 1*factorial(0). Now going to the start we see that

factorial(3) = 3*2*1*factorial(0).

When $m=0$, we satisfy the if clause and so factorial(0) returns $1$. Therefore factorial(3)=3*2*1*1=6.

Now we see that each time through the function, we multiply by some value and decrease the counter. This us to the following loop variant:

int factorial(int m){
    int temp = 1;
    while(m > 0){
        temp *= m;
        --m;
    }
    return temp;
}

These two functions should return the same result when you run factorial(3). The problem you gave is different, but very similar to this.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.