Recursion means that a function calls itself. Recursive functions do a small part of an entire task in each recursive call, similar to a loop. In fact, looping and recursion are typically alternate ways to do the same thing. Typically, an algorithm written recursively can be re-written using a loop. In many cases, recursion can simplify your code and make algorithms easier to understand. However, there are also some cases where using recursion makes your program confusing and inefficient. It takes experience and judgment to make the best choice between recursion and looping in particular cases.
When writing a recursive function, there should always be at least one base case. It is needed because otherwise, the series of recursive calls have no stopping point: they will halt only when they "blow the stack" and your program crashes. For most recursive functions, this is usually done with an if statement checking to see if one of the parameters reaches a certain value. For instance, if we are recursively calculating the factorial function, we check to see if our argument is 1, in which case we just return 1, rather than making a recursive call. We need multiple base cases when a recursive call makes more than one recursive call: for instance, for instance, recursively calculating the nth Fibonacci number involves calculating the nth - 1 Fibonacci number and the nth - 2 Fibonacci number. Therefore, that recursive code needs two base cases.
Each recursive step should do a small portion of the overall task. This is similar to the body of a loop. The small portion of the task could be done before you call the function again, or afterwards.
A recursive function would, of course, have at least one recursive call, or it's not a recursive function! The function calls itself, but with new parameters. In general, the parameter that is tested in the base case test should get closer to the base case with each recursive call so that the sequence of recursive calls will eventually end. Note: if there is a non-void return type for the function, you have to make sure that you return a result from each call: students sometimes get the recursive calls correct but fail to correctly return a value from those calls.
One way of writing recursive functions is to assume the function works on a subset of the problem. Assuming the function does what it's supposed to on the next recursive call, what do we need to add to make it complete? For example, if we are recursively summing a data structure, and we assume the call sum(n - 1) worked, what else do we need to do? Well, add n to that sum, of course! So we would write: return n + sum(n - 1)
You can find more on recursion here.