Thread: 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

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

one more good example is to calculate factoraial.

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

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.

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.

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.