Understanding Recursion in Python

Understanding recursion in Python

lets walk through the execution.

fact(5):
   5 is not 0, so fact(5) = 5 * fact(4)
   what is fact(4)?
fact(4):
   4 is not 0, so fact(4) = 4 * fact(3)
   what is fact(3)?
fact(3):
   3 is not 0, so fact(3) = 3 * fact(2)
   what is fact(2)?
fact(2):
   2 is not 0, so fact(2) = 2 * fact(1)
   what is fact(1)?
fact(1):
   1 is not 0, so fact(1) = 1 * fact(0)
   what is fact(0)?
fact(0):
   0 IS 0, so fact(0) is 1

Now lets gather our result.

fact(5) = 5* fact(4)

substitute in our result for fact(4)

fact(5) = 5 * 4 * fact(3)

substitute in our result for fact(3)

fact(5) = 5 * 4 * 3 * fact(2)

substitute in our result for fact(2)

fact(5) = 5 * 4 * 3 * 2 * fact(1)

substitute in our result for fact(1)

fact(5) = 5 * 4 * 3 * 2 * 1 * fact(0)

substitute in our result for fact(0)

fact(5) = 5 * 4 * 3 * 2 * 1 * 1 = 120

And there you have it. Recursion is the process of breaking a larger problem down by looking at it as successfully smaller problems until you reach a trivial (or "base") case.

Trouble understand recursion function python

def myfactorial(n):
    if n == 1: 
        return [1]
    else: 
        return myfactorial(n-1) + [n * myfactorial(n-1)[n-2]]

This is probably easiest to visualise with a small n value

When n = 2, we skip the if and go to the else loop

return myfactorial(1) + [2 * myfactorial(1)[0]] 
# Then, since if n == 1 we return [1] from myfactorial()
return [1] + [2 * [1][0]]
return [1] + [2]
return [1, 2]

Similarly, we can do something similar for n = 3

return myfactorial(2) + [3 * myfactorial(2)[1]]
# Since we know from the above that myfactorial(2) = [1, 2]
return [1, 2] + [3 * [1, 2][1]]
return [1, 2] + [3 * 2]
return [1, 2, 6]

And, for interests sake, for n = 4

return myfactorial(3) + [4 * myfactorial(3)[2]]
return [1, 2, 6] + [4 * [1, 2, 6][2]]
return [1, 2, 6, 24]

Need help understanding recursion flow of this Python function

Using a print statement is one of the best to analyze (for a beginner). You can run the below code to see exactly what is happening(I just inserted print statements at appropriate places).

class Solution(object):
    def _permuteHelper(self, nums, start=0):
        if start == len(nums) - 1:
            print('Returns: ',[nums[:]])
            return [nums[:]]
        result = []
        print("Start: ",start)
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            print("Swapped:", start," ", i)
            result += self._permuteHelper(nums, start + 1)
            nums[start], nums[i] = nums[i], nums[start]
        return result
    def permute(self, nums):
        return self._permuteHelper(nums)

print(Solution().permute([1, 2, 3])

Output:

Start:  0
Swapped: 0   0
Start:  1
Swapped: 1   1
Returns:  [[1, 2, 3]]
Swapped: 1   2
Returns:  [[1, 3, 2]]
Swapped: 0   1
Start:  1
Swapped: 1   1
Returns:  [[2, 1, 3]]
Swapped: 1   2
Returns:  [[2, 3, 1]]
Swapped: 0   2
Start:  1
Swapped: 1   1
Returns:  [[3, 2, 1]]
Swapped: 1   2
Returns:  [[3, 1, 2]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

Trying to understand recursion - Why is my function reaching maximum recursion or None?

All your branches are recursive - i.e. they all call the function again. So, you don't actually have a base case. The base case is the one where you actually can compute or return a value directly, instead of recursively computing one.

Consider another problem that you could solve with recursion: finding the sum of numbers in a list:

The base case is when you have the empty list and since there are no values, the sum is just 0.

To think about the recursive case you can slice the list:
the first item is a single number and the rest of the list is just another list. The sum for that case is then that first item plus the sum of the rest of the list:

>>> def find_sum(values):
...     if len(values) == 0:
...             return 0
...     else:
...             return values[0] + find_sum(values[1:])
... 
>>> find_sum([1, 2, 3])
6
>>>

I don't know what the Collatz sequence is, so I'll leave it to others to comment on how the recursion should look for that.

Understanding recursion with the Fibonacci Series

When in doubt, just break it down.

Sample Image

The tree flow is actually counter-intuitive to the actual control flow, but once you understand the sequence of calls, it becomes clearer. The thing to understand here is that you keep breaking down a larger computation to a sum of smaller computations, and you stop when you hit the base case (the if statements). Now you can carry out all the small computations, and combining the results of those small computations to form a bigger, larger result, until you have your final answer.

Every time a recursive call hits the base case, it will return either 1, or 0, depending on what case was hit. This value will be returned to the previous caller. To understand, consider:

f(1)₃ + f(0)₃

Note here that the subscript represents the depth of the recursion call tree. The call is made by f(2)₂. f(1)₃ is computed first, and 1 is returned to f(2)₂. f(0)₃ is then computed, and 0 is returned to f(2)₂. The two return values are summed, and the result is 1.

f(2)₂ then returns 1 to whoever called it, which in this case happens to be f(3)₁. f(3)₁ called f(2)₂ + f(1)₂, meanwhile this other f(1)₂ also returns 1 to f(3)₁, who now adds that with the result of f(2)₂, to form 2.

f(3)₁ now passes 2 to f(4)₀, its caller, which happened to call f(3)₁ + f(2)₁ ... and so it goes.

An alternative way of looking at this is to start from the first function call that is actually made: f(4)₀.

f(4)₀ computes f(3)₁ + f(2)₁. But to compute f(3)₁, it needs to know f(2)₂ + f(1)₂, and similarly, to compute f(2)₁, it needs to know f(1)₂ + f(0)₂, and so on.

Understanding Recursion in Tree Traversal

Like my comment suggests, you're not only printing "done with ..." for leaf nodes; instead you're doing that for every node in the tree, even intermediary ones.

I suggest changing your function as follows in order to see this more clearly:

def preOrderPrint(node):
    if node is not None:
        print(node.val)
        preOrderPrint(node.leftChild)
        print('Done with left node of node', node.val)
        preOrderPrint(node.rightChild) 
        print('Done with right node of node', node.val)

your output should now be:

6
4
2
Done with left node of node 2
Done with right node of node 2
Done with left node of node 4
5
...

Understanding recursion using power set example

If you add an "indentation" parameter to your function, while you explore it, you can immediately see which function calls which:

def subsets(nums):
        inp = nums
        out = []
        result=[]
        def helper(indent,inp,out,index):
            print(f"{indent}->helper({inp},{out},{index})")
            if index==len(inp):
                result.append(out)
                return
            helper(indent+'--',inp,out,index+1)
            helper(indent+'--',inp,out+[inp[index]],index+1)
        helper('',inp,out,0)
        return result

The result will look like:

->helper([1, 2, 3],[],0)
--->helper([1, 2, 3],[],1)
----->helper([1, 2, 3],[],2)
------->helper([1, 2, 3],[],3)
------->helper([1, 2, 3],[3],3)
----->helper([1, 2, 3],[2],2)
------->helper([1, 2, 3],[2],3)
------->helper([1, 2, 3],[2, 3],3)
--->helper([1, 2, 3],[1],1)
----->helper([1, 2, 3],[1],2)
------->helper([1, 2, 3],[1],3)
------->helper([1, 2, 3],[1, 3],3)
----->helper([1, 2, 3],[1, 2],2)
------->helper([1, 2, 3],[1, 2],3)
------->helper([1, 2, 3],[1, 2, 3],3)

So you can immidiately see why you get [] first--you get it when you go all the way through the list without including anything in the results. You get [3] next because you backtrack to the call where you add 3 and then go to the end. You get [2] by backtracking a bit further, to where you include 2 in the output, and then down the path that doesn't add 3. Then you get [2,3] because you backtrack one level up, to the call that has 2 included in the result, and this time go to the path that adds 3.

It probably isn't the easiest way to compute a power-set, though. There is a one-to-one correspondence between the powerset of size n and the binary numbers between 0 and 2**n-1. For each number, the 1-bits indicate which elements to include in the set. So you can also compute the powerset like this:

def subsets(nums):
    return [
        [nums[j] for j, b in enumerate(reversed(format(i, 'b'))) if b == '1']
        for i in range(2**len(nums))
    ]

It runs in exponential size, but so does the recursive version, and that is unavoidable when the output is exponential in the size of the input.

Understanding Recursion and Multiple Returns

One clarification which can help you understand what's going on: return ...X and ...Y means: Compute the value of X. If the value is false, return it, otherwise compute the value of Y, and return it.

More info about the short-circuit, lazy behavior (i.e. not evaluating Y if not needed) of the and and or operators in Python: https://docs.python.org/release/2.7/reference/expressions.html#boolean-operations

So that statement doesn't make the function return two values (X and Y), but one value which is the logical AND of X and Y: it's true iff both X and Y are (evaluated to) true.

Also it's worth distinguishing function from function call. There can be many active calls to the same function, with different arguments, local variables etc., so their return values can also be different (as soon as they return). When a function calls itself, that's called recursion. When a function call returns, execution continues in the caller, which can be the same function (but of course a different, upper-level function call) in case of recursion.

understanding recursion stack sum_integers

The 0 + 1 + 2 + sum_integers(3) = 0 + 1 + 2 + 3 is not really correct, an easier way to see it could be

sum_integers(3)             # go down in recursion
3 + sum_integers(2)         # go down in recursion
3 + 2 + sum_integers(1)     # go down in recursion
3 + 2 + 1 + sum_integers(0) # go down in recursion
3 + 2 + 1 + 0               # stop because 'return 0'
3 + 2 + 1                   # go back and apply the plus
3 + 3                       # go back and apply the plus
6                           # go back and apply the plus

Understanding Recursion in Python