# Simple Pseudocode Question

1. Sep 2, 2010

### mohabitar

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. Sep 3, 2010

### 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?

3. Sep 3, 2010

### mohabitar

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?

4. Sep 3, 2010

### 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?

5. Sep 3, 2010

### mohabitar

Foo(3,5,a)=2+Foo(4,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.

6. Sep 3, 2010

### Staff: Mentor

Foo(2,5,a)
= 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.