Web Development

  Homes arrow Web Development arrow Lesson 16: Recursion--a function calling itse...
 Webmaster Tools
 
Base64 Encoding 
Browser Settings 
CSS Coder 
CSS Navigation Menu 
Datetime Converter 
DHTML Tooltip 
Dig Utility 
DNS Utility 
Dropdown Menu 
Fetch Content 
Fetch Header 
Floating Layer 
htaccess Generator 
HTML to PHP 
HTML Encoder 
HTML Entities 
IP Convert 
Meta Tags 
Password Encryption
 
Password Strength
 
Pattern Extractor 
Ping Utility 
Pop-Up Window 
Regex Extractor 
Regex Match 
Scrollbar Color 
Source Viewer 
Syntax Highlighting 
URL Encoding 
Web Safe Colors 
Forums Sitemap 
Weekly Newsletter
 
Developer Updates  
Free Website Content 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Contact Us 
Site Map 
Privacy Policy 
Support 
 USERNAME
 
 PASSWORD
 
 
  >>> SIGN UP!  
  Lost Password? 
WEB DEVELOPMENT

Lesson 16: Recursion--a function calling itself
By: Developer Shed
  • Search For More Articles!
  • Disclaimer
  • Author Terms
  • Rating:  stars stars stars stars stars / 0
    2003-08-09

    Table of Contents:

    Rate this Article: Poor Best 
      ADD THIS ARTICLE TO:
      Del.ici.ous Digg
      Blink Simpy
      Google Spurl
      Y! MyWeb Furl
    Email Me Similar Content When Posted
    Add Developer Shed Article Feed To Your Site
    Email Article To Friend
    Print Version Of Article
    PDF Version Of Article
     
     

    SEARCH DEV MECHANIC

    TOOLS YOU CAN USE

    advertisement

    Recursion

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

    Recursion is defined as a function calling itself. It is in some ways similar to a loop because it repeats the same code, but it requires passing in the looping variable and being more careful. Many programming languages allow it because it can simplify some tasks, an it is often more elegant than a loop.

    A simple example of recursion would be:

    
    void recurse()
    {
    recurse(); //Function calls itself
    }
    int main()
    {
    recurse(); //Sets off the recursion
    return 0;  //Rather pitiful, it will never be reached
    }
    This program will not continue forever, however. The computer keeps function calls on a stack and once too many are called without ending, the program will terminate. Why not write a program to see how many times the function is called before the program terminates?
    
    #include <iostream.h>
    void recurse(int count) //The count variable is initalized by each function call
    {
    cout<<count;
    recurse(count+1); //It is not necessary to increment count
    //each function's variables
    } //are separate (so each count will be initialized one greater)
    int main()
    {
    recurse(1);        //First function call, so it starts at one
    return 0;
    }
    
    This simple program will show the number of times the recurse function has been called by initializing each individual function call's count variable one greater than it was previous by passing in count+1. Keep in mind, it is not a function restarting itself, it is hundreds of functions that are each unfinished with the last one calling a new recurse function.

    It can be thought of like those little chinese dolls that always have a smaller doll inside. Each doll calls another doll, and you can think of the size being a counter variable that is being decremented by one.

    Think of a really tiny doll, the size of a few atoms. You can't get any smaller than that, so there are no more dolls. Normally, a recursive function will have a variable that performs a similar action; one that controls when the function will finally exit. The condition where the functin will not call itself is termed the base case of the function. Basically, it is an if-statement that checks some variable for a condition (such as a number being less than zero, or greater than some other number) and if that condition is true, it will not allow the function to call itself again. (Or, it could check if a certain condition is true and only then allow the function to call itself).

    A quick example:
    
    void doll(int size)
    {
    if(size==0)//No doll can be smaller than 1 atom (10^0==1) so doesn't call itself
    return;    //Return does not have to return something, it can be used
    //to exit a function
    doll(size-1);  //Decrements the size variable so the next doll will be smaller.
    }
    int main()
    {
    doll(10);   //Starts off with a large doll (its a logarithmic scale)
    return 0;   //Finally, it will be used
    }
    
    This program ends when size equals one. This is a good base case, but if it is not properly set up, it is possible to have an base case that is always true (or always false).

    Once a function has called itself, it will be ready to go to the next line after the call. It can still perform operations. One function you could write could print out the numbers 123456789987654321. How can you use recursion to write a function to do this? Simply have it keep incrementing a variable passed in, and then output the variable...twice, once before the function recurses, and once after...
    
    void printnum(int begin)
    {
    cout<<begin;
    if(begin<9)  //The base case is when begin is greater than 9
    printnum(begin+1);    //for it will not recurse after the if-statement
    cout<<begin;  //Outputs the second begin, after the program has
    //gone through and output
    } //the numbers from begin to 9.
    
    This function works because it will go through and print the numbers begin to 9, and then as each printnum function terminates it will continue printing the value of begin in each function from 9 to begin.

    This is just the beginning of the usefulness of recursion. Heres a little challenge, use recursion to write a program that returns the factorial of any number greater than 0. (Factorial is number*number-1*number-2...*1).

    Hint: Recursively find the factorial of the smaller numbers first, ie, it takes a number, finds the factorial of the previous number, and multiplies the number times that factorial...have fun, email me at webmaster@cprogramming.com if you get it.



    << Back

     

    DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.

    More Web Development Articles
    More By Developer Shed

       

    WEB DEVELOPMENT ARTICLES

    - On Page SEO for New Domains
    - Improve Your Site`s Speed
    - Safari Books Online Review
    - Creating an Estore From the Ground Up
    - Most Common SEO Mistakes Developers Make
    - Making the Most of Your Titles and Meta Desc...
    - Five Ways Using Flash Can Damage Your Site
    - A Web Designer`s Guide to Colors
    - Use Webstarts to Create a Free Site
    - More Than Just Looks. How Your Web Design C...
    - How to Design Content Pages
    - Mint Review
    - Make Your WordPress Website Look Professional
    - How to Create a Mobile Web Site
    - Meta Tags: Still Useful?

    Developer Shed Affiliates

     



    © 2003-2018 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap