recursion?

This is a discussion on recursion? within the C++ Programming forums, part of the General Programming Boards category; can someone explain more or less what recursion does and what it is useful for? i don't need any code, ...

  1. #1
    Registered User heat511's Avatar
    Join Date
    Dec 2001
    Posts
    169

    recursion?

    can someone explain more or less what recursion does and what it is useful for?

    i don't need any code, i mostly understand it, but not what i am attempting to accomplish using recursion

    thanks

  2. #2
    Registered User
    Join Date
    Nov 2001
    Posts
    24
    recursion is just a function that calles itself untill a argument is met

    Code:
    void function(int number)
    {
    	if(number<=1)
    		return;
    	function(number/2);
    	cout<<number;
    }
    lets say that the number 4 is passed to the function it will:
    check 4<=1
    call function(2)
    check 2<=1
    call function(1)
    check 1<=1
    return
    cout 2
    cout 4
    end function
    hope this helps, remember to always have a base case or your recursion will run forever (or intill you run out of memory)

    Skeptic

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    4
    one more good example is to calculate factoraial.

    factorial(int n)
    {
    if(n==1)
    return 1;
    else
    return n*factorial(n-1);
    }

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    23
    Recursion is a way to simplify code. There is ALWAYS a base case (if you forget this step you will get an infinite loop) which will exit the function. Recursion will not work for everything.. a good way to test if you can make a recursive function is to see if you have a while() loop to calculate something repeatedly. For example like the given example above my post for factorial...

    Code:
    int factorial(int n)
      int temp = n;
      int counter = 1;
      while (counter != n) {
        temp *= counter;
        counter++;
      };
      
      return temp;
    }//end factorial
    Just remember recursion is just a tool...it is not necessary but it will help you with shortening code and simplifying things. My professor always talks about not looking into the "black box". Basically know the input and know the output and know how to divide up the input up repeatedly until it gets to the output.

  5. #5
    ¡Amo fútbol!
    Join Date
    Dec 2001
    Posts
    2,136
    However, recursion is not good if the function calls itself many times. For example, if you wanted to find the factorial of numbers around 50, you should use loops.

  6. #6
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    The best way to understand recursion
    is to understand induction. Basically you
    write some code which is correct for a base case, and then you design your algorithm so that if it is correct for a k <= n, where n is fixed, then it is correct for n + 1. An example would be merge sort where you assume that your algorithm is correct for sorting arrays of length <= n: A[0..n/2] and A[n/2+1..n] and then you merge the two sorted arrays together. The base case is of course when n = 1 or n = 0.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 08:45 PM
  2. convert Recursion to linear can it be done
    By umen242 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 02:58 AM
  3. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  4. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 09:56 AM
  5. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 08:24 AM

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