Recursive Definition

Question

Consider the following informal definition for a function calc(x,y) = (0*y) + (1*y) + … + (x*y) For example, we have that calc(2,5) = (0*5) + (1*5) + (2*5) Give a recursive definition for the function calc. Give a trace to show each step involved in calculating calc(3,4) using your definition.

I've come up with:

Base Case:

Calc(0,y) = 0

Recursive Case:

Calc(x,y) = n + Calc(x-1,y) * y

Some how I have a feeling my recursive case isn't going to work as expected.

Can somebody help me with this?

Of course your recursive case isn't going to work: what is $n$? where did that come from? :) — BrianO, Dec 14 '15 at 04:58
@BrianO I thought I might need a variable to store the total. Besides that, is there anything else you see that shouldn't be there? x — M-R, Dec 14 '15 at 05:00
Calc($x-1$,$y$)$*y$ should give you $y^2+2y^2+...(x-1)y^2$. Hopefully, you can see the problem here. — Kevin Long, Dec 14 '15 at 05:01
@KevinLong Yeah, can see why that's happening. Just don't know how to fix it. — M-R, Dec 14 '15 at 05:02

score 1 · Answer 1 · answered Dec 14 '15 at 05:01

1

The $n$ in your recursive case is not defined, so will cause failure. Your approach is correct, so $n$ should be replaced by $Calc(x,y)-Calc(x-1,y)$. What is the value of that? The recursive call will supply $Calc(x-1,y)$

answered Dec 14 '15 at 05:01

Ross Millikan

374,822

Recursive Definition

1 Answers1