Recursion “A Picture is Worth 1,500 Words”

What is Recursion?

Recursion means “defining a problem in terms of itself”. This can be a very powerful tool in writing algorithms. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as:

F(i) = F(i-1) + F(i-2).

Recursion is the process of defining a problem (or the solution to a problem) in terms of (a simpler version of) itself. For example, we can define the operation “find your way home” as:

1.If you are at home, stop moving.

2.Take one step toward home.

3.“find your way home”.

Here the solution to finding your way home is two steps (three steps). First, we don’t go home if we are already home. Secondly, we do a very simple action that makes our situation simpler to solve. Finally, we redo the entire algorithm.

The above example is called tail recursion. This is where the very last statement is calling the recursive algorithm. Tail recursion can directly be translated into loops.

Parts of a Recursive Algorithm:

All recursive algorithms must have the following:

1.Base Case (i.e., when to stop)

2.Work toward Base Case

3.Recursive Call (i.e., call ourselves)

Phase 1: input loop In this phase, the input is checked to meet the requirements of the base case, and if it fails, the function is called with different parameters. This continues until Phase 2 .

Phase 2 : Reference case In this phase, the entry corresponds to the base case and the function returns without further recursion.

Phase 3: loop back Finally, when the base case is reached and a value has been returned, previous function calls can resolve any statements that depend on the return value of their recursive call. When these calls return, the function “evolves”, so to speak, as each instance of the function stops executing from the line on which the recursive call was made.

the call stack :

In order to keep track of all function calls, functions are pushed onto the call stack . The call stack (or stack for short, although not all stacks are call stacks), is a region of memory of a fixed size, typically around 1MB. A stack of this size can handle a recursion depth of around 10,000 depending on the size of the stack frame. If a function repeats too many times, it can potentially run out of stack memory, causing a stack overflow . Each time a function is called, it is pushed onto the stack. Each time a function returns, it is extracted of the battery. Only the function at the top of the stack will run at a time.

example

Here is a function that uses a recursive algorithm to calculate xthe ypower.

First of all, whenever you are working with a recursive function, the first thing to clarify is the base case. This represents the condition in which the recursive function will stop calling itself and return.

In this example, we see that the base case corresponds to the first one if it is conditional, this is the base case:

if (y == 0)
        return (1);

Recursive declaration: decrement increment and y call the _pow_recursion function with y + 1 or y -1: if y is a positive integer, and -1 will decrease to 0 (if y is a negative integer, it will increase to 0)

if (y < 0)
        return (_pow_recursion(x, y + 1) / x);
return (_pow_recursion(x, y - 1) * x);