Velocity Reviews > recursion.

# recursion.

pereges
Guest
Posts: n/a

 04-09-2008
AS I understand, there must be a stopping condition in recursive
functions.

suppose my function is like this -

void build_kdtree(kdnode *kd, int axis, int depth)
{

if(kd->maxspheres <= MINSPHERES || depth >= DEPTHLIMIT)
{
kd->left = kd->right = NULL;

}

else
{

,,,,,,,,

build_kdtree(kd->left, axis, depth+1);
build_kdtree(kd->right, axis, depth+1);

}

My question is -

1. Is the stopping condition in if sufficient or some return value is
also necessary
2. Is this a right way to build a recursive function ?

Chris Dollin
Guest
Posts: n/a

 04-09-2008
pereges wrote:

> AS I understand, there must be a stopping condition in recursive
> functions.

In a non-lazy language like C, yes.

> suppose my function is like this -
>
> void build_kdtree(kdnode *kd, int axis, int depth)
> {
>
> if(kd->maxspheres <= MINSPHERES || depth >= DEPTHLIMIT)
> {
> kd->left = kd->right = NULL;
>
> }
>
> else
> {
>
> ,,,,,,,,
>
> build_kdtree(kd->left, axis, depth+1);
> build_kdtree(kd->right, axis, depth+1);
>
> }
>
> My question is -
>
> 1. Is the stopping condition in if sufficient or some return value is
> also necessary

You don't need a return value "just because" the function's recursive.

> 2. Is this a right way to build a recursive function ?

Looks plausible; can't tell without knowing more about the domain.

--
"Some of these", Hazleton had said, looking at a /A Clash of Cymbals/
just-completed tangle of wires, lenses, antennae and
kernels of metal with rueful respect, "ought to prove pretty potent in the
pinch. I just wish I knew which ones they were."

Hewlett-Packard Limited registered office: Cain Road, Bracknell,
registered no: 690597 England Berks RG12 1HN

pereges
Guest
Posts: n/a

 04-09-2008
On Apr 9, 5:51 pm, Chris Dollin <(E-Mail Removed)> wrote:

> > 2. Is this a right way to build a recursive function ?

>
> Looks plausible; can't tell without knowing more about the domain.

Well, kdtree is a binary tree where every node has a left child and
right child. IF I was making a recursive program for binary tree, then
if the stopping condition is satisfied what should I do ? I would make
the left and right child of this node null as it is a leaf node. but i
was wondering if this was sufficient as i have seen quite a few
recursive programs which do return a value.

Chris Dollin
Guest
Posts: n/a

 04-09-2008
pereges wrote:

> On Apr 9, 5:51 pm, Chris Dollin <(E-Mail Removed)> wrote:
>
>> > 2. Is this a right way to build a recursive function ?

>>
>> Looks plausible; can't tell without knowing more about the domain.

>
> Well, kdtree is a binary tree where every node has a left child and
> right child. IF I was making a recursive program for binary tree, then
> if the stopping condition is satisfied what should I do ?

The right thing -- whatever that is. There are many different
recursive programs on binary trees, so without knowing more
about what problem you're solving it's hard to be more specific.

> I would make
> the left and right child of this node null as it is a leaf node. but i
> was wondering if this was sufficient as i have seen quite a few
> recursive programs which do return a value.

Your function is called `build_kdtree`, but it appears to traverse
an existing tree, and the interesting stuff is buried in the elipsis
",,,,,,,,". So I'm confused.

You return a value if you need a value returned, and not if you
don't.

(fx:google) Ah, I find a definition of kd-tree. Don't you need
some points to construct the tree over, and not just a deph & axis?

--
"Its flagships were suns, its smallest vessels, /The City and the Stars/
planets."

Hewlett-Packard Limited Cain Road, Bracknell, registered no:
registered office: Berks RG12 1HN 690597 England

Ben Bacarisse
Guest
Posts: n/a

 04-09-2008
pereges <(E-Mail Removed)> writes:

> On Apr 9, 5:51 pm, Chris Dollin <(E-Mail Removed)> wrote:
>
>> > 2. Is this a right way to build a recursive function ?

>>
>> Looks plausible; can't tell without knowing more about the domain.

>
> Well, kdtree is a binary tree where every node has a left child and
> right child. IF I was making a recursive program for binary tree, then
> if the stopping condition is satisfied what should I do ? I would make
> the left and right child of this node null as it is a leaf node. but i
> was wondering if this was sufficient as i have seen quite a few
> recursive programs which do return a value.

That is cargo cult programming[1]. You are in charge -- it is your
program. You decide if you need a value and if so what. If you don't
need one, don't have one!

Also, rather than ask: "if the stopping condition is satisfied what
should I do?" you should ask "what is the recursive algorithm for
algorithm. When you understand that, what to do in various situation
will be clearer. Without the algorithm, no one can answer you
question.

[1] http://en.wikipedia.org/wiki/Cargo_cult_programming

--
Ben.