CODEWITHSUNDEEP
recursion
JCCV
JCCV

Reputation: 75

Trying to understand this simple recursion code

Please help me understand this simple recursion. I'm very new to programming, so I'm wondering how exactly this happens step by step.

I'm trying to learn recursion, but I'm stuck with the addition of "+"

function foo($bar) {
  if ($bar == 1) return 1;
  elseif ($bar == 0) return 0;
  else return foo($bar - 1) + foo($bar - 2);
}

Upvotes: 0

Views: 101

Answers (3)

Benjamin Danger Johnson
Benjamin Danger Johnson

Reputation: 1221

it's simple really (once you wrap your head around it). In the last line you are calling the function foo twice and adding their return values together.

here is a sample trace

call 1:
    foo(3)
    return foo(2) + foo(1)

    call 2:
        foo(2)
        return foo(1) + foo(0)

        call 3:
            foo(1)
            return 1

    unrolls to call 2:
        return 1 + foo(0)

        call 4:
            foo(0)
            return 0

    unrolls to call 2 again:
        return 1 + 0

unrolls to call 1:
    return 1 + foo(1)

    call 5:
        foo(1)
        return 1

unrolls to call 1 again:
    return 1 + 1

Upvotes: 1

Jordan Kaye
Jordan Kaye

Reputation: 2887

When trying to understand recursion I find it helps a lot to write down each individual case for a specific parameter and then build your understanding from there.

So let's take the example of foo(3)

foo(3) -> we don't hit either base case, so our function now wants to return 

foo(2) + foo(1)

First we need to get foo(2)

foo(2) -> Again no base case, so we return

foo(1) + foo(0)

foo(1) = 1 and foo(0) = 0 (these are our base cases) so we see that 

foo(2) = 1 + 0

Now our look at foo(3) is resolved to

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

foo(1) = 1, so we can finally see that

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

You have to remember that recursion is basically building a "tree" of function calls - it's going to go as far down the tree as possible, and then come up one level and see what else it has to do to continue. I'm not sure how clear this is but hopefully it helps.

Upvotes: 1

Eric J.
Eric J.

Reputation: 150228

The first invocation of foo() ends up calling two additional invocation of foo(). Each of those two in turn calls two of their own, and so on.

First Iteration

foo()

Second Iteration

foo() foo()

Third Iteration

foo() foo() foo() foo()

etc.

So, if foo() does not hit one of the termination conditions, it always calls itself twice more.

It may be instructive to add a variable indicating the call depth and having foo() print out its arguments including the call depth argument.

Upvotes: 0

Related Questions