CODEWITHSUNDEEP
recursion
user178822
user178822

Reputation: 53

Recursion by repeated addition

Here's a code that produces output as 11 by using recursion(Taking the value of a as 7). I'm unable to find how. Could anyone explain me how the functions stack up by calling itself producing this output?

int fun(int a)
        {
          if( a <= 1)
             return a;
          return fun(a-1) + fun(a-2) + fun(a-3);
        }

Upvotes: 0

Views: 259

Answers (1)

cdlane
cdlane

Reputation: 41905

Let's have fun with this as we examine how it works. I'm going to substitute Python equivalent code for reasons I'll show in the next step:

def fun(a):
    if a <= 1:
        return a

    return fun(a - 1) + fun(a - 2) + fun(a - 3)

b = fun(7)

print(b)

TEST

% python3 test.py
11
%

Now comes the fun, as we'll make one small change to our Python code. Instead of:

return a

we'll write:

return "+" + str(a)

Now when we run the code, we get:

% python3 test.py
+1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1+1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1+1+0+-1+1+0+1+0+-1+1
%

Which gives us a sense of how it works. All numbers are eventually reduced to a sequence of -1s , 0s and/or 1s and it's the sum of those that's our result. These three values all evaluate to themselves and are not expanded further. Knowing:

-1 -> +-1
0 -> +0
1 -> +1

We can see:

2 -> 2-1 2-2 2-3 -> 1 0 -1 -> +1+0-1 -> 0

3 -> 3-1 3-2 3-3 -> 2 1 0 -> (+1+0-1)+1+0 -> 1

And so forth. We can run 6, 5, & 4 through the program and concatenate those results to get the result for 7:

6 +1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1+1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0
5 +1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1
4 +1+0+-1+1+0+1+0+-1+1

7 +1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1+1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0[ ]+1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1[ ]+1+0+-1+1+0+1+0+-1+1

Finally, we'll add a line to the end of our modified Python program:

print(eval("0" + b))

Which will sum the string of zeros, ones and minus ones back into a number:

% python3 test.py
+1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1+1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1+1+0+1+0+-1+1+1+0+-1+1+0+1+0+-1+1+0+-1+1+0+1+0+-1+1
11
%

Which confirms that it's by summing up all these small numbers, produced by recursion, that we get our result.

Upvotes: 1

Related Questions