could any one help me in understanding the concepts of recursive fns.

This is a discussion on could any one help me in understanding the concepts of recursive fns. within the C Programming forums, part of the General Programming Boards category; i have a problem of understanding the recursive functions.I could not get the logic of implementing them correctly . I ...

  1. #1
    Registered User
    Join Date
    Aug 2004
    Posts
    8

    could any one help me in understanding the concepts of recursive fns.

    i have a problem of understanding the recursive functions.I could not get the logic of implementing them correctly .
    I want to learn them because it is one of the most important concepts of c.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I want to learn them because it is one of the most important concepts of c.
    I wouldn't say that, but recursion is a nice tool.

    >I could not get the logic of implementing them correctly .
    A function is a thingie (technical term) that holds stuff (highly technical term). Each thingie has it's own stuff, so you can make new thingies that look the same and it looks like you're using the same thingie inside of a thingie.

    That didn't work? Okay, when you call a function, a new instance of all of the function's variables (along with return addresses and such) are placed in an activation record. This activation record could look something like this:

    Local variables
    Arguments
    Return address
    Link to the previous record

    For the sake of pretty pictures, let's represent the above activation record like this:

    func:
    ----------
    |A|B|C|D|
    ----------

    Now, when you call a function it places a new activation record with the necessary items on the stack (if there is no stack, it simulates that behavior, so we say it's on the stack to avoid drawn out explanations meant for accuracy...like this one). When you have two functions and one of them calls the other, a new activation record for that function is placed on top of the current record. This causes execution to enter the new function. When the new function returns, the activation record is popped from the stack and execution returns back to the calling function. The "stack" would look like this after the function call:

    callee:
    ----------
    |A|B|C|D|
    ----------
    caller:
    ----------
    |A|B|C|D|
    ----------

    What if the callee is the same function as the caller?
    Code:
    void caller ( void )
    {
      if ( something )
        return;
    
      caller();
    }
    The exact same thing happens. A new activation record is created and pushed onto the stack:

    caller:
    ----------
    |A|B|C|D|
    ----------
    caller:
    ----------
    |A|B|C|D|
    ----------

    It appears as if the same function is being run a second time, but in fact it is a completely different function that just happens to use the same template for the activation record as the calling function.

    With the underlying concept understood (I hope), we can move on to the logic of implementing recursive functions. When designing a recursive function you usually just have to trust that it will work correctly, but the one thing that you must have is a base return condition. When the function has called itself enough times to solve the problem, you need a way to test for this and start the return path:
    Code:
    #include <stdio.h>
    
    void print ( int n )
    {
      if ( n == 0 )
        return;
    
      printf ( "%d ", n );
      print ( n - 1 );
      printf ( "%d ", n );
    }
    
    int main ( void )
    {
      print ( 5 );
      printf ( "\n" );
    
      return 0;
    }
    If the function does not have a test (it could be anything) where one branch does not result in a recursive call, you have infinite recursion. New activation records will keep getting pushed onto the stack until you run out of some critical resource and the program crashes with a stack overflow error or something similar.

    There are two rules for writing a recursive function: Each new recursive call should bring you closer to solving the problem and there must be a base case to end recursion.

    Also remember that there are two paths for recursive execution, the path in and the path out. Both are shown in the code given above. The execution could be traced like this:
    Code:
    n = 5, print and recurse
      n = 4, print and recurse
        n = 3, print and recurse
          n = 2, print and recurse
            n = 1, print and recurse
              n = 0, return
            n = 1, print and return
          n = 2, print and return
        n = 3, print and return
      n = 4, print and return
    n = 5, print and return
    The output you get is:
    Code:
    5 4 3 2 1 1 2 3 4 5
    That's really all there is to it, you just have to wrap your mind around the concepts and you'll find yourself enjoying the power of recursion. It is a very useful feature of C when you get into complex algorithms and data structures.
    My best code is written with the delete key.

  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    536
    Trivia question for the day: Who is the first to have said

    To iterate is human, to recurse is divine.
    Dave

  4. #4
    ... kermit's Avatar
    Join Date
    Jan 2003
    Posts
    1,528
    Originally posted by Dave Evans
    Trivia question for the day: Who is the first to have said
    To iterate is human, to recurse is divine.
    Dave
    Hi Dave,

    I came across the name L. Peter Deutsch, a couple of times with regards to the quote you posted.

    ~/
    Last edited by kermit; 08-29-2004 at 08:35 AM.

  5. #5
    Registered User
    Join Date
    Apr 2004
    Posts
    173
    For most recursive functions you just have to 'trust' that it works. I would suggest that you start with some of the more basic recursive functions and work out some exercises on recursion. After that, if you have done data structures before, try doing some binary tree problems since they are recursive in nature. Thats how I got to understand a bit more about recursive functions

    Also this may help a bit - as Prelude said you need a base case and each recursive call should work towards fulfulling that case. Also, for some of the more complex stuff, just take the simplest possible case and understand the logic to derive the recursive functions.

    For example, if you had a big binary search tree, and you wanted to write a function that printed out all the information pre-order'edly, instead of trying to figure out how the whole thing is going to work, just look at a basic unit (say 1 parent and 2 children). If it works for that, then you can assume it will work with the rest of the tree for example. Then again I probably don't make much sense though

  6. #6
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    Posts
    501
    The linux kernel uses recursive functions to follow symbolic links, so they are very applicable. They are very useful to know about.
    Help populate a c/c++ help irc channel
    server: irc://irc.efnet.net
    channel: #c

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. understanding recursive functions
    By houler in forum C Programming
    Replies: 7
    Last Post: 12-09-2004, 11:56 AM
  2. Replies: 11
    Last Post: 08-30-2004, 03:56 PM
  3. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21