Recursive functions

[NotionCommotion]

The following script produces the following results.  Okay, so I am not returning from recursive($c) and getting to echo("d: $d "); until $c is zero, and am then echoing the previous local variable values.  Not what I wanted.

<?php
function recursive($c)
{
    echo("c: $c ");
    --$c;
    if($c>0) {
        $d=recursive($c);
        echo("d: $d ");
        //return $d;
    }
    echo("\nreturn c: $c\n");
    return $c;
}

$a=5;
echo("a = $a\n");

$b=recursive($a);
echo("\nb = $b");

a = 5
c: 5 c: 4 c: 3 c: 2 c: 1 
return c: 0
d: 0 
return c: 1
d: 1 
return c: 2
d: 2 
return c: 3
d: 3 
return c: 4

b = 4

Modifying the script to return recursive($c) results in the following.  Assuming these are the desired results, anything wrong (i.e. could be made more efficient) with it?

<?php
function recursive($c)
{
    echo("c: $c ");
    --$c;
    if($c>0) {
        $d=recursive($c);
        echo("d: $d ");
        return $d;
    }
    echo("\nreturn c: $c\n");
    return $c;
}

$a=5;
echo("a = $a\n");

$b=recursive($a);
echo("\nb = $b");

a = 5
c: 5 c: 4 c: 3 c: 2 c: 1 
return c: 0
d: 0 d: 0 d: 0 d: 0 
b = 0

 

Edited July 16, 2017 by NotionCommotion

[requinix]

See, we're back to abstract questions again.

 

If you're just trying to understand or practice recursion then the code is fine. Recursion has two parts: the recursive part that decides whether to go into the recursion or not, and the non-recursive part that happens when the recursion is not supposed to happen. If either is missing or flawed then you might crash PHP - that's the hard crash, not the fatal error crash.

Your code has both that are, apparently, working as intended. Great. But using something like the Fibonacci sequence will be a better exercise.

 

If you're using this as an example of real code then the code is not fine. There is no reason to use recursion to count from 5 to 0. It's wasteful. Of course that should already be obvious.

[NotionCommotion]

Everyone seems to dislike abstract questions.  I tend to like them!  It allows one to focus on a specific issue.  Yeah, I know the risk of that whole xy problem, and how some people hate them, but to each his own.

 

My purpose of this post was to just better understand recursion, however, I was hoping that knowledge would help me solve my non-abstract problem.

 

I have an application where canisters contain other canisters as well as marbles.  I wish to retrieve all canisters and marbles only where the marbles have some given property.  See, even now, I can't help but try to abstractify it   Switch  marbles to real points and canisters to virtual points...

 

To implement it, I have the following tables. The application will enforce that one and only one of tables pointsReal, pointsVirtual, or pointsNotApplicable will be joined to points. pointsNotApplicable is well, not applicable, and the application will prevent it from ever being joined to pointsVirtual_has_points, and only pointsReal and pointsVirtual will be joined to pointsVirtual_has_points.

 

I wish to return all records in the points table which meet the following criteria:

 

1. Limited to a LIKE clause on points.name (don't need any help on this one)

 

AND (

 

2. Limit to where pointsVirtual_has_points JOINs points to pointsReal and pointsReal.trend is not zero (this one is also okay)

 

OR

 

3. Limit to where pointsVirtual_has_points JOINs points to pointsVirtual, and pointsVirtual_has_points isn't JOINing the resultant record to pointsReal where pointsReal.trend is zero. Note that pointsVirtual_has_points can be recursively JOINed to another pointsVirtual, however, it is expected that it will never exceed four or so levels.

)

 

I am concerned that it might not be possible solely with SQL, and will need to utilize script to iterate over the results.  Can this be done solely with SQL?  If not, any recommendations how to do so using PHP?  Is using the Fibonacci sequence applicable?

 

Thanks

 

 

CREATE TABLE IF NOT EXISTS points (
id INT NOT NULL,
name VARCHAR(45) NOT NULL,
type ENUM('real', 'virtual', 'NotApplicable') NOT NULL,
PRIMARY KEY (id))
ENGINE = InnoDB;

CREATE TABLE IF NOT EXISTS pointsReal (
id INT NOT NULL,
trend TINYINT NOT NULL,
PRIMARY KEY (id),
CONSTRAINT fk_pointsReal_points
FOREIGN KEY (id)
REFERENCES points (id)
ON DELETE NO ACTION
ON UPDATE NO ACTION)
ENGINE = InnoDB;

CREATE TABLE IF NOT EXISTS pointsVirtual (
id INT NOT NULL,
PRIMARY KEY (id),
CONSTRAINT fk_pointsVirtual_points1
FOREIGN KEY (id)
REFERENCES points (id)
ON DELETE NO ACTION
ON UPDATE NO ACTION)
ENGINE = InnoDB;


CREATE TABLE IF NOT EXISTS pointsVirtual_has_points (
pointsVirtual_id INT NOT NULL,
points_id INT NOT NULL,
PRIMARY KEY (pointsVirtual_id, points_id),
INDEX fk_pointsVirtual_has_points_points1_idx (points_id ASC),
INDEX fk_pointsVirtual_has_points_pointsVirtual1_idx (pointsVirtual_id ASC),
CONSTRAINT fk_pointsVirtual_has_points_pointsVirtual1
FOREIGN KEY (pointsVirtual_id)
REFERENCES pointsVirtual (id)
ON DELETE NO ACTION
ON UPDATE NO ACTION,
CONSTRAINT fk_pointsVirtual_has_points_points1
FOREIGN KEY (points_id)
REFERENCES points (id)
ON DELETE NO ACTION
ON UPDATE NO ACTION)
ENGINE = InnoDB;

CREATE TABLE IF NOT EXISTS pointsNotApplicable (
id INT NOT NULL,
bla VARCHAR(45) NULL,
PRIMARY KEY (id),
CONSTRAINT fk_pointsNotApplicable_points1
FOREIGN KEY (id)
REFERENCES points (id)
ON DELETE NO ACTION
ON UPDATE NO ACTION)
ENGINE = InnoDB;

Edited July 16, 2017 by NotionCommotion

[requinix]

I like abstract questions too. The problem is when someone takes their real problem and dumbs it down into a simpler question and in the process loses some of the intricacies that make an answer to the simple question be incorrect or invalid for the original problem. Having an abstract question is one thing, deriving an abstract version of a concrete problem is another.

 

If you required that it was never more than 4 levels deep then that opens the door to other ideas. If you can alter the table structures then there's a couple more to consider.

 

How about some possibly unnecessary questions. How often will you need to do a query like this? How often will you add, change, or remove points? Would you say that "few", "some", or "many" of the points will be virtual?

Will you be querying containers in the middle of a hierarchy, or just the container at the top? Will you only ever be identifying children of a virtual point, or sometimes going backwards too? Can a virtual point have virtual and non-virtual children?

[NotionCommotion]

I could mandate the number of levels to 4.  I could also alter the table structure if necessary provided it doesn't impact other aspects of the application.  To better describe the application...

 

The user "creates" real points and virtual points, and also "creates" aggregate points of either real or virtual points.  That "pointsNotApplicable" table I originally mentioned is really "pointsAggregate" whose PK is a 1-two-1 to points, and includes the meta data (foreign back to points {application prevents it from being to another aggr point} and a time duration) to produce the min/max/avg of either a real point or virtual point (but not another aggregate point).   This "create" phase will not be performed too often, but displaying the values of these three point types will be performed often.

 

In regards to your questions:

• How often will you need to do a query like this?  Fairly often when doing an autocomplete search.
• How often will you add, change, or remove points?  Not often.
• Would you say that "few", "some", or "many" of the points will be virtual? Few: Expected 80% real, 15% aggr, 5% virtual.
• Will you be querying containers in the middle of a hierarchy, or just the container at the top?  I think ideally at the top, but maybe need to do middle to implement
• Will you only ever be identifying children of a virtual point, or sometimes going backwards too?  I am pretty sure I will need to go both directions, but only starting at one pole or the other.
• Can a virtual point have virtual and non-virtual children?  Yes

 

Thanks for your help!

[requinix]

If you're not modifying the data often then how about a table just dedicated to the ancestor/descendant relationship?

  1
 / \
2   3
   / \
  4   5

a | d
--+--
1 | 2
1 | 3
1 | 4
1 | 5
3 | 4
3 | 5

[NotionCommotion]

If you're not modifying the data often then how about a table just dedicated to the ancestor/descendant relationship?

 

I don't know.  It just doesn't smell right, and almost always when I have done something like this, it has later came back to bite me.  If later I added 6 to 5, I would have to do the same to 1 and 3 opposed to doing it just once using my original schema.  I recognize I stated retrieval happens much more frequently than adds/mods, but I don't know yet whether a traditional implementation will have performance issues, and would rather go that approach until I know for sure.

a | d
--+--
1 | 2
1 | 3
3 | 4
3 | 5
5 | 6

[requinix]

It just doesn't smell right, and almost always when I have done something like this, it has later came back to bite me.

You'd have to be careful to maintain integrity, but some constraints and even triggers can make that easier.

 

If later I added 6 to 5, I would have to do the same to 1 and 3 opposed to doing it just once using my original schema.

To be clear, it would be three total queries instead of one:

1. Insert the point/virtual point relationship (duh)

2. Insert the 5/6 relationship

3.

INSERT INTO relationships (from, to)
SELECT from, 6 FROM relationships WHERE to = 5

I recognize I stated retrieval happens much more frequently than adds/mods, but I don't know yet whether a traditional implementation will have performance issues, and would rather go that approach until I know for sure.

It probably won't have "issues", like anything particularly noticeable, but with an arbitrary depth and an arbitrary number of siblings you can't avoid the recursive nature of the problem.

 

...unless you go with nested sets. I mentioned changing the schema earlier because nested sets would solve the recursion problem: it increases the cost to add or remove items, makes it significantly harder to get immediate children of a parent, but makes it crazy easy to get all descendants of an item.

Before              After

id | left | right   id | left | right
---+------+------   ---+------+------
 1 |    1 |    10    1 |    1 |    12
 2 |    2 |     3    2 |    2 |     3
 3 |    4 |     9    3 |    4 |    11
 4 |    5 |     6    4 |    5 |     6
 5 |    7 |     8    5 |    7 |    10
                     6 |    8 |     9

So if adding and removing is relatively rare and needing immediate children is even less frequent then nested sets can go well. There's also a hybrid approach of the standard parent/child relationship plus nested sets, which would give you all the advantages when reading but all the disadvantages when writing. Edited July 17, 2017 by requinix
adding before/after

[Psycho]

I like abstract questions too. The problem is when someone takes their real problem and dumbs it down into a simpler question and in the process loses some of the intricacies that make an answer to the simple question be incorrect or invalid for the original problem. Having an abstract question is one thing, deriving an abstract version of a concrete problem is another.

 

+10 There is nothing that frustrates me more than taking my personal time to provide a solution for the exact problem someone posts only to have them come back and make a statement along the lines of it doesn't work for the problem they really have which is different from what they posted.

[NotionCommotion]

...unless you go with nested sets. I mentioned changing the schema earlier because nested sets would solve the recursion problem: it increases the cost to add or remove items, makes it significantly harder to get immediate children of a parent, but makes it crazy easy to get all descendants of an item.

Before              After

id | left | right   id | left | right
---+------+------   ---+------+------
 1 |    1 |    10    1 |    1 |    12
 2 |    2 |     3    2 |    2 |     3
 3 |    4 |     9    3 |    4 |    11
 4 |    5 |     6    4 |    5 |     6
 5 |    7 |     8    5 |    7 |    10
                     6 |    8 |     9

So if adding and removing is relatively rare and needing immediate children is even less frequent then nested sets can go well. There's also a hybrid approach of the standard parent/child relationship plus nested sets, which would give you all the advantages when reading but all the disadvantages when writing.

 

 

I've looked into nested sets in the past, and felt that they often are a last resort.  If I didn't go with your duplicated data ancestor/descendant idea, I would rather just use php to perform some recursion and run multiple queries (i.e. 4 or so if four levels deep) and use prepared statements if possible (won't be if I use an IN (...) query).  Or maybe I do have some db options using https://mariadb.com/kb/en/mariadb/with/

[NotionCommotion]

+10 There is nothing that frustrates me more than taking my personal time to provide a solution for the exact problem someone posts only to have them come back and make a statement along the lines of it doesn't work for the problem they really have which is different from what they posted.

 

 

When adding this post, my sole goal was only to better understand how PHP can perform recursion, and I promise to never comeback later and say any responses that promotes this goal did not solve my problem.  While I appreciate how requinix expanded the breadth of this question, I was not expected so.  I know it is frustrating sometimes as how recursion should be implemented surely depends on the details of the application, but I also didn't want to weigh everyone down on details about my particular database application.  How would you recommend I ask "generic" questions in the future?  Thanks

[kicken]

How would you recommend I ask "generic" questions in the future?

You could just not ask generic questions. There's no rule that says one can't ask a detailed/specific question, you just have to provide enough details for one to understand it. Coming up with a sufficient analogy to ask a question about isn't always easy. I've struggled a few times to do so and as such try to avoid doing so generally.

 

Despite your marble/canister analogy (from devshed) and having tables I still really have no idea what kind of data you're trying to work with or why. That makes it near impossible to recommend a solution, either in PHP or in SQL. Example data + desired result sets might go a long way toward clarifying things.

 

Based on your marbel/canister analogy created a script that will generate the tables and some test data (for SQL Server, not Mysql). If my guess at your data is relatively accurate then maybe the example below would help. If it's not you'll have to explain some more I suppose.

if object_id('pointsVirtual_has_points') is not null drop table pointsVirtual_has_points;
if object_id('pointsNotApplicable') is not null drop table pointsNotApplicable;
if object_id('pointsReal') is not null drop table pointsReal;
if object_id('pointsVirtual') is not null drop table pointsVirtual;
if object_id('points') is not null drop table points;
GO

CREATE TABLE points (
  id INT NOT NULL identity(1,1),
  name VARCHAR(45) NOT NULL,
  type varchar(15) NOT NULL,
  PRIMARY KEY (id));

CREATE TABLE pointsReal (
  id INT NOT NULL,
  trend TINYINT NOT NULL,
  PRIMARY KEY (id),
  CONSTRAINT fk_pointsReal_points
    FOREIGN KEY (id)
    REFERENCES points (id)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION);

CREATE TABLE pointsVirtual (
  id INT NOT NULL,
  PRIMARY KEY (id),
  CONSTRAINT fk_pointsVirtual_points1
    FOREIGN KEY (id)
    REFERENCES points (id)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
;


CREATE TABLE pointsVirtual_has_points (
  pointsVirtual_id INT NOT NULL,
  points_id INT NOT NULL,
  PRIMARY KEY (pointsVirtual_id, points_id),
  CONSTRAINT fk_pointsVirtual_has_points_pointsVirtual1
    FOREIGN KEY (pointsVirtual_id)
    REFERENCES pointsVirtual (id)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION,
  CONSTRAINT fk_pointsVirtual_has_points_points1
    FOREIGN KEY (points_id)
    REFERENCES points (id)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
;

CREATE TABLE pointsNotApplicable (
  id INT NOT NULL,
  bla VARCHAR(45) NULL,
  PRIMARY KEY (id),
  CONSTRAINT fk_pointsNotApplicable_points1
    FOREIGN KEY (id)
    REFERENCES points (id)
    ON DELETE NO ACTION
    ON UPDATE NO ACTION)
;
GO

INSERT INTO points (Name, Type) 
VALUES ('Red marbel 1', 'real')
 , ('Red marbel 2','real')
 , ('Red marbel 3','real')
 , ('Red marbel 4','real')
 , ('Red marbel 5','real')
 , ('Green marbel 1','real')
 , ('Green marbel 2','real')
 , ('Green marbel 3','real')
 , ('Green marbel 4','real')
 , ('Green marbel 5','real')
 , ('Blue marbel 1','real')
 , ('Blue marbel 2','real')
 , ('Blue marbel 3','real')
 , ('Blue marbel 4','real')
 , ('Blue marbel 5','real')
;

INSERT INTO points (Name, Type)
VALUES ('Red Bag', 'virtual')
 , ('Green Bag', 'virtual')
 , ('Blue Bag', 'virtual')
 , ('RG Bag', 'virtual')
 , ('GB Bag', 'virtual')
 , ('RB Bag', 'virtual')
 , ('Everything', 'virtual')
 ;

INSERT INTO pointsReal (id, trend)
SELECT
    id, ROW_NUMBER() OVER (PARTITION BY SUBSTRING(Name, 1, CHARINDEX(' ', Name)-1) ORDER BY id)
FROM points
WHERE
    type='real'
;

INSERT INTO pointsVirtual (id)
SELECT
    id
FROM points
WHERE
    type='virtual'
;

INSERT INTO pointsVirtual_has_points (pointsVirtual_id, points_id)
SELECT
    pointsVirtual.id
    , pset.id
FROM pointsVirtual
INNER JOIN points vpoint ON vpoint.id = pointsVirtual.id
INNER JOIN points pset ON pset.Name LIKE (SUBSTRING(vpoint.name, 1, CHARINDEX(' ', vpoint.name)) + '%')
WHERE
    vpoint.Name != 'Everything'
    AND vpoint.id != pset.id
;

INSERT INTO pointsVirtual_has_points (pointsVirtual_id, points_id)
SELECT
    (SELECT id FROM points WHERE Name='RG Bag')
    , id
FROM points
WHERE
    Name IN ('Red Bag', 'Green Bag')
;

INSERT INTO pointsVirtual_has_points (pointsVirtual_id, points_id)
SELECT
    (SELECT id FROM points WHERE Name='GB Bag')
    , id
FROM points
WHERE
    Name IN ('Green Bag', 'Blue bag')
;

INSERT INTO pointsVirtual_has_points (pointsVirtual_id, points_id)
SELECT
    (SELECT id FROM points WHERE Name='RB Bag')
    , id
FROM points
WHERE
    Name IN ('Red Bag', 'Blue Bag')
;

INSERT INTO pointsVirtual_has_points (pointsVirtual_id, points_id)
SELECT
    (SELECT id FROM points WHERE Name='Everything')
    , id
FROM points
WHERE
    Name IN ('Red Bag', 'Green Bag', 'Blue bag')
;
GO

Or maybe I do have some db options using https://mariadb.com/kb/en/mariadb/with/

If you have access to recursive queries using a WITH statement then something like this may be what you're looking for:

WITH cte AS (
    SELECT 
        p.id as parentId
        , p.type as type
        , p.Name as name
        , map.points_id as childId
    FROM points p
    LEFT JOIN pointsVirtual v ON v.id = p.id
    LEFT JOIN pointsVirtual_has_points map ON map.pointsVirtual_id=v.id
    WHERE
        p.Name = 'Everything'
    UNION ALL
    SELECT 
        p.id as parentId
        , p.type as type
        , p.name as name
        , c.id as childId
    FROM cte 
    INNER JOIN points p ON p.id = cte.childId
    INNER JOIN pointsVirtual v ON v.id = p.id
    INNER JOIN pointsVirtual_has_points map ON v.id = map.pointsVirtual_id
    INNER JOIN points c ON c.id = map.points_id
    UNION ALL
    SELECT
        p.id as parentId
        , p.type as type
        , p.name as name
        , NULL as childId
    FROM cte
    INNER JOIN points p ON p.id = cte.childId
    WHERE
        p.type = 'real'
)
SELECT
    *
FROM cte

Such a query should grab all the relevant rows but the final result may still need a little clean up work done in PHP.

 

If you don't have the ability to do a recursive query like the above and you can guarantee that it won't recurse down too many times then just doing a function in PHP to gather the results through recursive queries would probably be fine, just try and minimize the queries as much as possible and be efficient with your processing. I've done things like this in the past with recursive menus and it's worked out fine since in pratice they never go more than about 5 levels deep and that is rare.

[NotionCommotion]

Thanks kicken,

 

I agree good analogies are tough!  It is definitely a lot easier just posting a huge specification and have others attempt to interpret it, but is that reasonable?

 

The marble/canister analogy was actually derived here during dialog with requinix, and I later added it over at devshed (hoping for rudy's sql ingenious!).  I actually think the analogy is quite good.

 

Yes, I have access to recursive queries as I for this purpose upgraded to mariadb 10.2, and appreciate your example script.  Also your rule of thumb advice about being able to do so using php recursion as long as the iterations are small is much appreciated.

 

Thanks again!

[NotionCommotion]

Turns out a full SQL solution was possible.

WITH RECURSIVE t AS (
SELECT p.id
FROM points_real pr
INNER JOIN points p ON p.id=pr.id
WHERE pr.trend=0
UNION ALL
SELECT pvhp.pointsVirtual_id
FROM pointsVirtual_has_points pvhp
INNER JOIN t ON t.id=pvhp.points_id
)
SELECT *
FROM points p LEFT OUTER JOIN t ON t.id=p.id
WHERE t.id IS NULL AND p.name LIKE "MB1%";