Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Simple Pseudocode Question

  1. Sep 2, 2010 #1
    I'm new to psuedocode, and I'm having trouble putting all the pieces together:

    Here is the definition of a function named foo whose inputs are two integers and an array of integers a[1] . . . a[n].

    Code (Text):
    1 Foo(k,m, a[1],...,a[n])
    2   if (k < 1 or m > n or k > m) return 0
    3   elsereturn a[k] +Foo(k+1,m,a[1],...,a[n])
    Suppose that the input integers are k = 2 and m = 5 and the input array contains 5,6,2,3,4,8,2. What value does Foo return? Using summation notation, give a general formula for what Foo computes.

    This one is making my head hurt. Here's what I did so far: So line 2 has three conditional statements: If k<1// if 2<1..this is false If m>n//if 5 is greater than the amount of values in the array, which is 7, so this is false If k>m // if 2> 5, this is false

    So this function will display line 3. So line 3 says: return a[k] which is a[2] which is the second value of the array, which is 6. So take 6 and add it to (2+1, 5, a[1].....,a[n])

    So is what I have done correct up there? If so, how would I know is a[n] is? Am I supposed to be finding that? What would be the final result of all this?
  2. jcsd
  3. Sep 3, 2010 #2


    Staff: Mentor

    The function doesn't display anything, but control passes to line 3.
    Not quite. The function returns 6 + Foo(3, 5, a[1], a[2], ..., a[n]), or IOW, 6 + Foo(3, 5, 5, 6, 2, 3, 4, 8, 2).

    Now, what does that evaluate to?
  4. Sep 3, 2010 #3
    Ahh ok I'm still confused. So this is a recursive function. The last line tells me to take 6 and add it to Foo(...), so doesnt Foo(...) just display line 3, which is 6+Foo(...). So I dont get it, do I keep adding and adding, when does it ever stop? Or am I looking at this the wrong way?
  5. Sep 3, 2010 #4


    Staff: Mentor

    Foo() does NOT display anything, it returns a value that involves a recursive call to Foo again.

    In the first call to Foo(), it returns 6 + Foo(3, 5, 5, 6, 2, 3, 4, 8, 2). Please answer the question I asked in my last post: What's the value of this expression?
  6. Sep 3, 2010 #5
    So it would start with Foo(2,5,a)=6+Foo(3,5,a)
    and so on until this whole thing returns o, correct? So the final output is zero?

    But now what about the 2nd part: Using summation notation, give a general formula for what Foo computes.

    I dont even know where to start with this one.
  7. Sep 3, 2010 #6


    Staff: Mentor

    = 6+Foo(3,5,a)
    = 6 + 2 + Foo(4, 5, a)
    = ?

    I'll take your word that the 3rd line above is correct. The "whole thing" won't return 0. Eventually, Foo(x, y, a) will return 0, but you need to add all the other values that have been returned, as in what I show above.

    Don't worry about the 2nd part until you understand what Foo is doing.

    For the third time, Foo does not display anything, and there is no output. The only thing Foo does is calculate some number by a recursive algorithm.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook