R-E-C-U-R-S-I-O-N

Ever heard of it?

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

43 Replies - 21042 Views - Last Post: 21 July 2005 - 11:53 AM Rate Topic: -----

Poll: What is your level of familiarity with recursion? (35 member(s) have cast votes)

What is your level of familiarity with recursion?

  1. Im an ex Lisp programmer. I wouldn't iterate with a gun to my head (2 votes [5.71%])

    Percentage of vote: 5.71%

  2. I work with a lot of trees and linked lists; I use recursion often (6 votes [17.14%])

    Percentage of vote: 17.14%

  3. I sometimes use recursion and am familiar with it (11 votes [31.43%])

    Percentage of vote: 31.43%

  4. I have heard of recursion, know the concept, but haven't used it (3 votes [8.57%])

    Percentage of vote: 8.57%

  5. I have heard of recursion but don't really know what it is (3 votes [8.57%])

    Percentage of vote: 8.57%

  6. Recursion? What? (10 votes [28.57%])

    Percentage of vote: 28.57%

Vote Guests cannot vote

#1 cyberscribe   User is offline

  • humble.genius
  • member icon

Reputation: 10
  • View blog
  • Posts: 1,062
  • Joined: 05-May 02

R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 02:43 PM

I'm contemplating writing an article on the power or recursion in PHP. With so many languages placing such heavy emphasis on iterative constructs, I think the when/how/why of recursion often gets sidelined.

I think the PHP d.i.c. community is pretty representative, with coders at all levels perusing the forums. So - cast your vote, post your comments - let me know what you think.
Is This A Good Question/Topic? 0
  • +

Replies To: R-E-C-U-R-S-I-O-N

#2 snoj   User is offline

  • Married Life
  • member icon

Reputation: 93
  • View blog
  • Posts: 3,583
  • Joined: 31-March 03

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 03:00 PM

This is prolly pretty stupid sounding, but what exactly is 'recursion'? Is it the use of user defined functions and classes?
Was This Post Helpful? 0
  • +
  • -

#3 skyhawk133   User is offline

  • Head DIC Head
  • member icon

Reputation: 1972
  • View blog
  • Posts: 20,425
  • Joined: 17-March 01

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 03:19 PM

Recursion is this:

-Level 1
    -Level 2
    -Level 2
    -Level 2
        -Level 3
             -Level4
    -Level 2
-Level 1



Recursion is a difficult concept to grasp at first, however, once you understand how it works, it's relatively simple.

There is 1 way, and 1 way only (correct me if I'm wrong Robert) to accomplish any type of recursion, and that is a function within itself. This allows for infinite looping over a query, folder structure, etc. etc.

I would be happy to help out with an article on recursion for ColdFusion if you would like.
Was This Post Helpful? 0
  • +
  • -

#4 MathewS   User is offline

  • D.I.C Regular

Reputation: 18
  • View blog
  • Posts: 349
  • Joined: 14-May 02

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 03:22 PM

ive heard of it now:P, but ive not had chance to use it for any projects yet.

Would be nice to see an article on this subject.
Was This Post Helpful? 0
  • +
  • -

#5 Amadeus   User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 253
  • View blog
  • Posts: 13,507
  • Joined: 12-July 02

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 03:27 PM

hotsnoj, on May 20 2004, 05:00 PM, said:

This is prolly pretty stupid sounding, but what exactly is 'recursion'? Is it the use of user defined functions and classes?

Simply put, recursion is generally a function that calls itself, or a process that calls itself, etc... It's extremely useful under the right circumstances, especially, as cyberscribe notes, with linked lists and some other data structures. As to why there is a heavier focus these days on iterative code, there's different schools of thought. One runs that the benefits don't always outweigh the learning curve sometimes associated with recursion. I disagree myself, I think recursion is great, when required, but it takes all types.

:)

This post has been edited by Amadeus: 20 May 2004 - 03:28 PM

Was This Post Helpful? 0
  • +
  • -

#6 skyhawk133   User is offline

  • Head DIC Head
  • member icon

Reputation: 1972
  • View blog
  • Posts: 20,425
  • Joined: 17-March 01

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 03:27 PM

To accomplish something like the above:

-Level 1
   -Level 2
   -Level 2
   -Level 2
       -Level 3
            -Level4
   -Level 2
-Level 1



You may have a database with categories... the columns would be:

cat_id
cat_name
cat_parent

So going back to the level example, you may have this:

-Fruits [ID: 1, Parent: NULL]
   -Oranges [ID: 2, Parent: 1]
   -Apples [ID: 3, Parent: 1]
   -Berries [ID: 4, Parent: 1]
       -Cherries [ID: 5, Parent: 4]
            -Pitless Cherries [ID: 6, Parent: 5]
   -Banana [ID: 7, Parent: 1]
-Vegtables [ID: 8, Parent: NULL]



The recursion is accomplished in the above example by using a unique ID for each record and a reference to the parent. Some recursion will reference a level to make it easier to display the tree structure, however, the only requirement is knowing what the parent is.
Was This Post Helpful? 0
  • +
  • -

#7 Amadeus   User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 253
  • View blog
  • Posts: 13,507
  • Joined: 12-July 02

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 03:35 PM

Here's an example in C from this site. A simple example, but a valid one.

int Factorial(int n)
{
    if (n==1)          
       return 1; 
    else 
        return Factorial(n-1) * n; 
} 


It can sometimes take a while to get the idea straight, but once you get it, you've got it forever. The questions is, do you want it? LOL :)

This post has been edited by Amadeus: 20 May 2004 - 04:48 PM

Was This Post Helpful? 0
  • +
  • -

#8 MathewS   User is offline

  • D.I.C Regular

Reputation: 18
  • View blog
  • Posts: 349
  • Joined: 14-May 02

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 03:50 PM

skyhawk133, on May 20 2004, 11:27 PM, said:

To accomplish something like the above:

-Level 1
   -Level 2
   -Level 2
   -Level 2
       -Level 3
            -Level4
   -Level 2
-Level 1



You may have a database with categories... the columns would be:

cat_id
cat_name
cat_parent

So going back to the level example, you may have this:

-Fruits [ID: 1, Parent: NULL]
   -Oranges [ID: 2, Parent: 1]
   -Apples [ID: 3, Parent: 1]
   -Berries [ID: 4, Parent: 1]
       -Cherries [ID: 5, Parent: 4]
            -Pitless Cherries [ID: 6, Parent: 5]
   -Banana [ID: 7, Parent: 1]
-Vegtables [ID: 8, Parent: NULL]



The recursion is accomplished in the above example by using a unique ID for each record and a reference to the parent. Some recursion will reference a level to make it easier to display the tree structure, however, the only requirement is knowing what the parent is.

oh i guess i have done a really basic version of that then :blink:
Was This Post Helpful? 0
  • +
  • -

#9 Cookie Mobster   User is offline

  • nooneenooneenooonee
  • member icon

Reputation: 8
  • View blog
  • Posts: 4,736
  • Joined: 12-October 01

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 04:00 PM

Recursion was one of the harder topics I remember from my various programming classes a few years back, but after I caught on to the principals I found it slightly useful, I've always just prefered using a loop to do the same thing that recursion does...
Was This Post Helpful? 0
  • +
  • -

#10 cyberscribe   User is offline

  • humble.genius
  • member icon

Reputation: 10
  • View blog
  • Posts: 1,062
  • Joined: 05-May 02

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 06:28 PM

Amadeus, on May 20 2004, 03:35 PM, said:

The questions is, do you want it? LOL :)

Yes - that's my question. Cookie Mobster points out he uses iteration for all his code needs. But for interesting data structures like linked lists and trees and even good old fashioned file systems with nested directories, you basically can't use iteration effectively because you don't know the depth or width of what you're dealing with before hand.

So far it looks like there's a pretty good split between, "I know about it and rarely use it" and, "Huh?" in the PHP community.

More votes! More votes!
Was This Post Helpful? 0
  • +
  • -

#11 caffinephreak   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 229
  • Joined: 08-July 02

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 09:19 PM

so recursion is more or less a special kind of loop?
from chris' example, I used plenty of it in comp sci(c++) last semester, but don't think i've done much recursion in php
Was This Post Helpful? 0
  • +
  • -

#12 skyhawk133   User is offline

  • Head DIC Head
  • member icon

Reputation: 1972
  • View blog
  • Posts: 20,425
  • Joined: 17-March 01

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 09:22 PM

caffinephreak, on May 20 2004, 10:19 PM, said:

so recursion is more or less a special kind of loop?

not so much a special kind of loop as much as the function which can call itself from within itself... going infinitely deep
Was This Post Helpful? 0
  • +
  • -

#13 caffinephreak   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 229
  • Joined: 08-July 02

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 10:20 PM

skyhawk133, on May 20 2004, 11:22 PM, said:

caffinephreak, on May 20 2004, 10:19 PM, said:

so recursion is more or less a special kind of loop?

not so much a special kind of loop as much as the function which can call itself from within itself... going infinitely deep

basicly what i meant, i just don't know the technical terms, kinda like this?
int Function(int num, int num2)
{
     if (num / num2 = 5)
          return num;
     else
         {
             num++
             Function(num, num2)
          }
}

Was This Post Helpful? 0
  • +
  • -

#14 cyberscribe   User is offline

  • humble.genius
  • member icon

Reputation: 10
  • View blog
  • Posts: 1,062
  • Joined: 05-May 02

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 10:50 PM

caffinephreak, on May 20 2004, 10:20 PM, said:

int Function(int num, int num2)
{
     if (num / num2 = 5)
          return num;
     else
         {
             Function(++num, num2)
          }
}

Yep, that's a recursive function. It doesn't aggregate as nicely as the factorial example, and it's a pretty scarry function to run if num/num2 starts out greater than 5. It's basically a recursive version of something that would traditionally be done iteratively. There are other examples where recursion makes even more sense.

Keep voting.
Was This Post Helpful? 0
  • +
  • -

#15 caffinephreak   User is offline

  • D.I.C Head

Reputation: 4
  • View blog
  • Posts: 229
  • Joined: 08-July 02

Re: R-E-C-U-R-S-I-O-N

Posted 20 May 2004 - 11:17 PM

yeah, i just pulled some code out of my ass on that one..but it got the point across. We spent about 2-3 weeks on this in comp sci, so I was pretty damn comfy with it, but I havn't done any real scripting in like, 4 months :(
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3