Book for recursion.....

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • AmberJain
    Recognized Expert Contributor
    • Jan 2008
    • 922

    Book for recursion.....

    HELLO,

    I studied recursion in C programming. But I still think that I'm unable to grab the concept of recursion. OR better said I cannot get recursion inside my mind from the book I'm referring to. So please tell me a book which will make me feel more comfortable with concept of recursion in programming.

    THANKS.......
  • JosAH
    Recognized Expert MVP
    • Mar 2007
    • 11453

    #2
    Recursion as programming knows it is all about divide and conquer. Briefly stated
    if a problem is too complex you chop it up in smaller instances of itself, fiddle
    a bit with the results and you're ready. If the program instance is very simple there
    is no need to chop it up but you solve it directly. This is the 'sentinel' condition.

    A canonical example is the binary tree; you can recursively define a binary tree
    as either nothing at all (the sentinel condition) or a node having two binary trees
    as its two children.

    Given this simple recursive definition a lot of problems are just corollaries thereof.
    e.g. the number of nodes in a tree either equals zero (the sentinel condition) or
    one plus the number of nodes of both of the children. In C this translates easily to:

    [code=c]
    int nof_nodes(tree_ t* node) {
    if (node == NULL)
    return 0;
    return 1+nof_nodes(nod e->left)+nof_node s(node->right);
    }
    [/code]

    Another example: the depth of a tree is the length of the longest path from the
    root of the tree to a leaf node; this translates to C as:

    [code=c]
    int depth(tree_t* node) {
    if (node == NULL)
    return 0;
    return 1+max(depth(nod e->left), depth(node->right));
    }
    [/code]

    Note the similarity of both functions. There is a simple rule of thumb: the depth
    of the stack must not exceed O(n) where n is the size of the problem. For nicely
    balanced trees this rule is true. Not so with a recursive definition of another
    problem: the factorial of a number either equals one if n equals 0 (the sentinel
    condition) or the product of n times the factorial of n-1. This translates to C as:

    [code=c]
    int fac(int n) {
    if (n == 0)
    return 1;
    return n*fac(n-1);
    }
    [/code]

    The depth of the stack will aways be O(n) and this function is better expressed
    in an iterative way:

    [code=c]
    int fac(int n) {
    int result= 1;
    for (; n > 0; result*= n--);
    return result;
    }
    [/code]

    Although this code looks more 'mechanical' it doesn't use any stack at all for its
    calculations. This rule of thumb doesn't work for functions with two or more
    variables; a famous example is the Ackermann function:

    [code=c]
    int act(int n, int m) {
    if (n == 0)
    return m+1;
    if (m == 0)
    return ack(n-1, 1);
    return ack(n-1, ack(n, m-1));
    }
    [/code]

    This little monster uses a horrible amount of stack space and it can't be written
    in an iterative way without using any form of a stack. A closed form of this function
    does exist but it needs the 'Knuth operator' or similar to be expressed in this
    closed form. A bit of theory on recursive functions and computability as well as
    Turing decidability can be found here.

    kind regards,

    Jos

    Comment

    • AmberJain
      Recognized Expert Contributor
      • Jan 2008
      • 922

      #3
      THANK YOU ............... ............... ............... ...
      Last edited by JosAH; Jul 13 '08, 05:39 PM. Reason: removed the verbatim copy of the previous reply

      Comment

      Working...