Change background image
  1. What's up? I see you're viewing as a Guest. How about registering, it only takes like 2 minutes. This will enable you to do more on our forum and stay updated.

Recursion

Discussion in 'Developer General' started by 3nvisi0n, Jul 7, 2011.

Thread Status:
This thread is more than 180 days old.
  1. 3nvisi0n

    3nvisi0n The R3v0lu710n Super-Mod

    Hello again,

    Definition:
    Recursious (noun): See 'Recursion' until understood.

    Okay that is a bit of a joke but that is the idea. Recursion is a programming concept that basically seperates the kiddies from real programmers. It isn't that recursion is difficult(it isn't) but most kids who learn to program don't learn programming concepts such as recursion

    Recursion is a basic concept used when you can divide a large problem into a series of similar smalller problems. The classic exmaple of recursion is the Fibonacci(fib from here on) numbers. If you are not familiar with the fib pattern let me show it to you:

    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ... infinity

    If you fail to see the pattern it is simply this: each number is the sum of the two numbers prior. So start with 0, 1 for the sake of starting then 0+1=1, 1+1=2, 2+1=3 and so on.

    So the big problem to be solved to calculating the numbers, the sub-problems are calculating the values for the 2 prior numbers. Thus the basic overall problem and subproblem is the same. If that is the case, then recusion can be used. Its a little convoluted but perhaps if you see it then it will make more sense.

    Where is this useful, well I've never actually written a program outside of academia requiring these numbers but they are found within mathematics and idealized nature. So there is potential but they simply demonstrate the recursion concept best.

    So how would you create a function to do this? Well the simplest way is via recursion(all recursion can be written with loops also)

    Since each Fib number 'n' = Fib numbers n-1 + Fib number n-2 the code could look something like this.

    function fib(int index) {
    return fib(index-1) + fib(index-2)
    }

    this would of course be an infinte loop of sorts, so we need a base-case one that can be figured out without needing to recurse(call itself) so the final function looks like this

    function fib(int index) {
    if(index<=0) return 0;
    if(index==1) return 1; //1st 2nums are the base case since they need no calculation to figure out
    return fib(index-1)+fib(index-2)
    }

    And there we have it using recursion to figure out any number in the Fib series.

    Now that you've seen it maybe it amkes a little more sense. Again the basic idea is to divide the problem into small similar sub-problems and then conquer. Where is this used for real:

    Parsing XML trees: when parsing an XML tree you want to recurse down all children in it. Ie, Find the root element then if element has a child element go to it.

    Recursive directory delete:
    rm -rf -r means recursive in otherwords it will delete recursivly, Working something like
    delete(folder)
    if(folder has subfolder)
    for all subfolders as sub -> delete(sub)
    rm folder
    else rm folder


    in other words it recurses down to the bottom directy and deletes the directories from the bottom up.
    In other programming this also works to simplify complex loops for example I had a program awhile ago that would stop except in a few special case. Instea of doing a weird do while loop. I just did if(specialCase) recurse()

    Recursion when you understand becomes a valuable tool to use in coding, albeit not the best way(overhead of function calls can become huge) It is an elegent solution to many programs and helps produce beautiful code simply. When you see recursive code you know you are dealing with someone who can think abstractly like a programmer. :)
Thread Status:
This thread is more than 180 days old.

Share This Page