DEV Community

Cover image for Recursion
Andrew Garcia
Andrew Garcia

Posted on • Updated on

Recursion

When reduced to a concise example, recursion can be quite a simple concept to grasp.

The below recursive function:

f(x,count)=10+x+f(x,count1)f(x,\mathrm{count}) = 10 + x + f(x,\mathrm{count - 1})

Takes a summand xx float and a count\mathrm{count} index which defines the number of recursions. The function decreases this index with every recursion, and terminates the function with a "0" when the count\mathrm{count} value becomes 0.
Defining this function in code:

#include <bits/stdc++.h>
using namespace std;

double recurAdd(double x, int count)
{
    if (count == 0){return 0;} // termination
    return 10 + x + recurAdd(x, count - 1);
}

// Driver code
int main()
{
    cout << recurAdd(0.5, 3);
    return 0;
}
Enter fullscreen mode Exit fullscreen mode

This small program will output 31.5 as a final value. We can represent the complete recursion in the following way:

f1=10+0.5+(10+0.5+(10+0.5(0)))f_1 = 10 + 0.5 + ( 10 + 0.5 + ( 10 + 0.5 (0) ) )

Where the recursion can be broken down in the following way, from its first to last input iteration:

f1=10+0.5+f2f2=10+0.5+f3f3=10+0.5+f4f4=0f_1 = 10 + 0.5 + f_2 \\ f_2 = 10 + 0.5 + f_3 \\ f_3 = 10 + 0.5 + f_4 \\ f_4 = 0

After the last input function f4f_4 has been terminated, the running of operations can be visualized to occur from the deepest f4f_4 to the outermost f1f_1 nest. I visualize this process with the following schematic:

Image description

Though not all recursion algorithms may follow this pattern, this visual has helped me simplify my understanding of recursion. I hope my visual helps you too.

-Andrew

Top comments (0)