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

Printable View

- 03-28-2002heat511recursion?
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 - 03-28-2002Skeptic
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;

}

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 - 03-29-2002usmadhav79
one more good example is to calculate factoraial.

factorial(int n)

{

if(n==1)

return 1;

else

return n*factorial(n-1);

} - 03-29-2002prophet
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

- 03-29-2002golfinguy4
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.

- 03-29-2002Nick
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.