Recursion in place of looping

This is a discussion on Recursion in place of looping within the C Programming forums, part of the General Programming Boards category; Hi there, I am a new commer to the programming world. And I am finding it difficulties in the 2 ...

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    2

    Lightbulb Recursion in place of looping

    Hi there,
    I am a new commer to the programming world. And I am finding it difficulties in the 2 questions :

    * What are the "difference between Recursion and Looping"?

    * What are the "conditions for which recursion can be used in place of looping"?

    If any body know about this, please help?
    Last edited by dnayak382; 02-06-2011 at 12:49 AM.

  2. #2
    Third Eye Babkockdood's Avatar
    Join Date
    Apr 2010
    Posts
    352
    goto statements, maybe? I don't know, recursion and looping sound like the same thing to me.

  3. #3
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by Babkockdood View Post
    goto statements, maybe? I don't know, recursion and looping sound like the same thing to me.
    They're not... a loop is a group of instructions repeated several times, recursion is when a function calls itself.

    Example for looping: test reading a file.
    Code:
    // single file test
    void TestFile(PVOID FName)
      { DWORD BytesRead = 1;
        if (!Scanning)
          return;
        ++ FileCount;
        HANDLE fh = CreateFile(FName,FILE_READ_DATA,FILE_SHARE_READ,NULL,
                                OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL | 
                                FILE_FLAG_NO_BUFFERING |
                                FILE_FLAG_SEQUENTIAL_SCAN,NULL);
        if (fh == INVALID_HANDLE_VALUE)
          { AddError(GetLastError(),FName);
            return; }
        while ((BytesRead > 0) && Scanning)
          { if (!ReadFile(fh,FileBuffer,BufferSize,&BytesRead,NULL))
              { PostMessage(WHandle[0],UM_ADDERR,GetLastError(),(LPARAM)FName);
                break; }
            ByteCount += BytesRead; }
        CloseHandle(fh); }

    Example for recursion: Tunneling down subdirectories in a file system.
    Code:
    // recursive directory search
    void TestDir(PVOID SPath)  
      { HANDLE HDir;
        ++ FolderCount;
        if (!SetCurrentDirectory(SPath))
          { PostMessage(WHandle[0],UM_ADDERR,GetLastError(),(LPARAM)SPath);
            return; }
        HDir = FindFirstFile("*.*",&DirData);
        if (HDir == INVALID_HANDLE_VALUE)
          { PostMessage(WHandle[0],UM_ADDERR,GetLastError(),0);
            return; }
        do
          { if (DirData.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
              {if (Recurse && (DirData.cFileName[0] != '.'))
                 TestDir(DirData.cFileName); } 
            else
              TestFile(DirData.cFileName); }
        while (FindNextFile(HDir,&DirData) && Scanning);
        FindClose(HDir);
        SetCurrentDirectory(".."); }
    Last edited by CommonTater; 02-05-2011 at 05:54 PM.

  4. #4
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    Is there ever a time when a recursive solution cannot be replaced by one using loops, or v.v? Certainly some problems will intuitively favor one over the other, but you can always use either, no?
    C is fun

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by CommonTater View Post
    They're not... a loop is a group of instructions repeated several times, recursion is when a function calls itself.
    If you're bored, google stackless recursion. You'll get something like this:

    Stack Free Recursion


    Quzah.
    Hope is the first step on the road to disappointment.

  6. #6
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by KBriggs View Post
    Certainly some problems will intuitively favor one over the other, but you can always use either, no?
    No. Absolutely not. They aren't the same thing at all.

    Recursion is not a looping technique, it is tunneling. It is a way of climing into heirarchies like file systems (disk folders) or linked lists. Strictly speaking you are not repeating the same code on the same data multiple times... you have a subroutine calling itself on different data each time.

    Take a look a the loop example I provided... it does exactly the same thing every time, round and round until the exit condition is met.

    Now look at the recursion example... When it calls itself to explore a new directory it's operating on a completely different data set that may or may not have it calling itself again for a new folder ... It's not a loop at all. It is drilling down into the folder structure, not running in a circle.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,445
    Quote Originally Posted by KBriggs
    Is there ever a time when a recursive solution cannot be replaced by one using loops, or v.v?
    No, it is always possible to rewrite the code from one to the other.

    Quote Originally Posted by KBriggs
    Certainly some problems will intuitively favor one over the other, but you can always use either, no?
    Yes. I'd say that CommonTater misread this: we're not saying that looping and recursion is the same thing, but that they can be used to achieve the same net effect (assuming no stack overflow and such).
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by dnayak382 View Post
    Specify the conditions for which recursion can be used in place of looping?
    I can think of two conditions:
    1. The original poster (dnayak382) shows an attempt to solve the problem by him or herself, and stops disguising an imperative as though it were a question.

    2. The other condition I wont share just yet, though another poster has essentially mentioned the condition.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Very new to C. Recursion ?
    By Jingleheimer in forum C Programming
    Replies: 3
    Last Post: 03-24-2008, 08:16 AM
  2. Recursion Revisited again, and again!
    By clegs in forum C++ Programming
    Replies: 93
    Last Post: 12-08-2007, 07:02 PM
  3. recursion error
    By cchallenged in forum C Programming
    Replies: 2
    Last Post: 12-18-2006, 08:15 AM
  4. stop a recursion
    By acosgaya in forum C++ Programming
    Replies: 5
    Last Post: 10-31-2006, 09:46 AM
  5. Printing a centric square using recursion
    By ChaosTheMatador in forum C Programming
    Replies: 1
    Last Post: 03-07-2006, 05:13 PM

Tags for this Thread


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