Tree Recursion

Tips for navigating the slides:
  • Press O or Escape for overview mode.
  • Visit this link for a nice printable version
  • Press the copy icon on the upper right of code blocks to copy the code

Class outline:

  • Order of recursive calls
  • Tree recursion
  • Counting partitions

Order of recursive calls

The cascade function


                    def cascade(n):
                        if n < 10:
                            print(n)
                        else:
                            print(n)
                            cascade(n//10)
                            print(n)
                    

What would this display?


                    cascade(123)
                    

                    1
                    12
                    123
                    12
                    1

                    123
                    12
                    1
                    12
                    123
                    

Cascade environment diagram


                            def cascade(n):
                                if n < 10:
                                    print(n)
                                else:
                                    print(n)
                                    cascade(n//10)
                                    print(n)

                            cascade(123)
                            
  • Each cascade frame is from a different call to cascade.
  • Until the Return value appears, that call has not completed.
  • Any statement can appear before or after the recursive call.
Global frame
cascade → func cascade(n)[parent=Global]
f1: cascade[parent=Global]
n 123
Return value None
f2: cascade[parent=Global]
n 12
Return value None
f3: cascade[parent=Global]
n 1
Return value None
Print output:

                                123
                                12
                                1
                                12
                                123
                                

Two definitions of cascade


                            def cascade(n):
                                if n < 10:
                                    print(n)
                                else:
                                    print(n)
                                    cascade(n//10)
                                    print(n)
                            

                            def cascade(n):
                                print(n)
                                if n >= 10:
                                    cascade(n//10)
                                    print(n)
                            
  • If two implementations are equally clear, then the shorter one is usually better
  • When learning to write recursive functions, put the base cases first
  • Both are recursive functions, even though only the first has typical structure

Inverse cascade

How can we output this cascade instead?


                    1
                    12
                    123
                    12
                    1
                    

Inverse cascade solution


                    def inverse_cascade(n):
                        grow(n)
                        print(n)
                        shrink(n)
                    
                    def f_then_g(f, g, n):
                        if n:
                            f(n)
                            g(n)
                    

                    grow = lambda n: f_then_g(grow, print, n//10)
                    shrink = lambda n: f_then_g(print, shrink, n//10)
                    

Tree recursion
(Multiple recursion)

Tree Recursion

Tree-shaped processes arise whenever a recursive function makes more than one recursive call.


Sierpinski curve

Recursive Virahanka-Fibonacci

The nth number is defined as:

$$\small\begin{equation*} \text{virfib}(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ \text{virfib}(n - 1) + \text{virfib}(n - 2) & \text{otherwise} \\ \end{cases} \end{equation*}$$


                    def virfib(n):
                        """Compute the nth Virahanka-Fibonacci number, for N >= 1.
                        >>> virfib(2)
                        1
                        >>> virfib(6)
                        8
                        """
                        if n == 0:
                            return 0
                        elif n == 1:
                            return 1
                        else:
                            return virfib(n-1) + virfib(n-2)
                    

A tree-recursive call graph

140489090487008 virfib(4) 140489896869120 virfib(3) 140489627348624 virfib(3) 140489090487008->140489627348624 (#2) 140489090487008->140489627348624:c 2 (#11) 140489627381168 virfib(2) 140489090487008->140489627381168 (#12) 140489090487008->140489627381168:c 1 (#17) 140489627327024 virfib(2) 140489896869120->140489627327024 (#20) 140489896869120->140489627327024:c 1 (#25) 140489896870176 virfib(1) 140489896869120->140489896870176 (#26) 140489896869120->140489896870176:c 1 (#27) 140489090487536 virfib(2) 140489627348624->140489090487536 (#3) 140489627348624->140489090487536:c 1 (#8) 140489090488912 virfib(1) 140489627348624->140489090488912 (#9) 140489627348624->140489090488912:c 1 (#10) 140489090398176 virfib(1) 140489627381168->140489090398176 (#13) 140489627381168->140489090398176:c 1 (#14) 140489627319936 virfib(0) 140489627381168->140489627319936 (#15) 140489627381168->140489627319936:c 0 (#16) 140489090488064 virfib(1) 140489090487536->140489090488064 (#4) 140489090487536->140489090488064:c 1 (#5) 140489896874064 virfib(0) 140489090487536->140489896874064 (#6) 140489090487536->140489896874064:c 0 (#7) 140489627309072 virfib(1) 140489627327024->140489627309072 (#21) 140489627327024->140489627309072:c 1 (#22) 140489627375904 virfib(0) 140489627327024->140489627375904 (#23) 140489627327024->140489627375904:c 0 (#24) 140489090486480 virfib(5) 140489090486480->140489090487008 (#1) 140489090486480->140489090487008:c 3 (#18) 140489090486480->140489896869120 (#19) 140489090486480->140489896869120:c 2 (#28) 99999999 Result 99999999->140489090486480:c 5 (#29)

Redundant computations

The function is called on the same number multiple times. 🙀

140489090487008 virfib(4) 140489896869120 virfib(3) 140489627348624 virfib(3) 140489090487008->140489627348624 (#2) 140489090487008->140489627348624:c 2 (#11) 140489627381168 virfib(2) 140489090487008->140489627381168 (#12) 140489090487008->140489627381168:c 1 (#17) 140489627327024 virfib(2) 140489896869120->140489627327024 (#20) 140489896869120->140489627327024:c 1 (#25) 140489896870176 virfib(1) 140489896869120->140489896870176 (#26) 140489896869120->140489896870176:c 1 (#27) 140489090487536 virfib(2) 140489627348624->140489090487536 (#3) 140489627348624->140489090487536:c 1 (#8) 140489090488912 virfib(1) 140489627348624->140489090488912 (#9) 140489627348624->140489090488912:c 1 (#10) 140489090398176 virfib(1) 140489627381168->140489090398176 (#13) 140489627381168->140489090398176:c 1 (#14) 140489627319936 virfib(0) 140489627381168->140489627319936 (#15) 140489627381168->140489627319936:c 0 (#16) 140489090488064 virfib(1) 140489090487536->140489090488064 (#4) 140489090487536->140489090488064:c 1 (#5) 140489896874064 virfib(0) 140489090487536->140489896874064 (#6) 140489090487536->140489896874064:c 0 (#7) 140489627309072 virfib(1) 140489627327024->140489627309072 (#21) 140489627327024->140489627309072:c 1 (#22) 140489627375904 virfib(0) 140489627327024->140489627375904 (#23) 140489627327024->140489627375904:c 0 (#24) 140489090486480 virfib(5) 140489090486480->140489090487008 (#1) 140489090486480->140489090487008:c 3 (#18) 140489090486480->140489896869120 (#19) 140489090486480->140489896869120:c 2 (#28) 99999999->140489090486480:c 5 (#29)

(We will speed up this computation dramatically in a few weeks by remembering results)

Counting partitions

Counting partitions problem

The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order.

count_partitions(6, 4) # n, m
2 + 4 = 6
1 + 1 + 4 = 6
3 + 3 = 6
1 + 2 + 3 = 6
1 + 1 + 1 + 3 = 6
2 + 2 + 2 = 6
1 + 1 + 2 + 2 = 6
1 + 1 + 1 + 1 + 2 = 6
1 + 1 + 1 + 1 + 1 + 1 = 6

Counting partitions approach

The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order.

count_partitions(6, 4) # n, m

Recursive decomposition: finding simpler instances of the problem.

Explore two possibilities:

  • Use at least one 4
  • Don't use any 4

Tree recursion often involves exploring different choices.

Counting partitions approach

The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order.

count_partitions(6, 4) # n, m

Solve two simpler problems:

count_partitions(2, 4)
count_partitions(n-m, m)
count_partitions(6, 3)
count_partitions(n, m-1)

Counting partitions code

The number of partitions of a positive integer n, using parts up to size m, is the number of ways in which n can be expressed as the sum of positive integer parts up to m in increasing order.

count_partitions(6, 4) # n, m

Solve two simpler problems:

with parts of size m:

count_partitions(2, 4)
count_partitions(n-m, m)

without parts of size m:

count_partitions(6, 3)
count_partitions(n, m-1)

                            def count_partitions(n, m):
                                """
                                >>> count_partitions(6, 4)
                                9
                                """
                                if n == 0:
                                    return 1
                                elif n < 0:
                                    return 0
                                elif m == 0:
                                    return 0
                                else:
                                    with_m = count_partitions(n-m, m)
                                    without_m = count_partitions(n, m-1)
                                    return with_m + without_m
                            

Count partitions call graph

140192484755264 count_partitions(2, 2) 140192485705712 count_partitions(4, 1) 140192485703680 count_partitions(0, 2) 140192484755264->140192485703680 (#2) 140192484755264->140192485703680:c 1 (#3) 140192485704208 count_partitions(2, 1) 140192484755264->140192485704208 (#4) 140192484755264->140192485704208:c 1 (#13) 140192485706240 count_partitions(3, 1) 140192485705712->140192485706240 (#16) 140192485705712->140192485706240:c 1 (#29) 140192485707296 count_partitions(4, 0) 140192485705712->140192485707296 (#30) 140192485705712->140192485707296:c 0 (#31) 140191948186192 count_partitions(1, 1) 140192485704208->140191948186192 (#5) 140192485704208->140191948186192:c 1 (#10) 140192485705184 count_partitions(2, 0) 140192485704208->140192485705184 (#11) 140192485704208->140192485705184:c 0 (#12) 140191948186720 count_partitions(0, 1) 140191948186192->140191948186720 (#6) 140191948186192->140191948186720:c 1 (#7) 140191948187360 count_partitions(1, 0) 140191948186192->140191948187360 (#8) 140191948186192->140191948187360:c 0 (#9) 140192487102560 count_partitions(2, 1) 140192485706240->140192487102560 (#17) 140192485706240->140192487102560:c 1 (#26) 140192485706768 count_partitions(3, 0) 140192485706240->140192485706768 (#27) 140192485706240->140192485706768:c 0 (#28) 140192487107616 count_partitions(1, 1) 140192487102560->140192487107616 (#18) 140192487102560->140192487107616:c 1 (#23) 140192487108672 count_partitions(2, 0) 140192487102560->140192487108672 (#24) 140192487102560->140192487108672:c 0 (#25) 140192488196016 count_partitions(0, 1) 140192487107616->140192488196016 (#19) 140192487107616->140192488196016:c 1 (#20) 140192487108144 count_partitions(1, 0) 140192487107616->140192487108144 (#21) 140192487107616->140192487108144:c 0 (#22) 140192488194912 count_partitions(4, 2) 140192488194912->140192484755264 (#1) 140192488194912->140192484755264:c 2 (#14) 140192488194912->140192485705712 (#15) 140192488194912->140192485705712:c 1 (#32) 99999999 Result 99999999->140192488194912:c 3 (#33)

Count partitions variant

To save on unneeded calls, we can cap m, the maximum partition size, based on n. We can also add a base case for m of size 1.


                def count_partitions(n, m):
                    if m == 1 or n == 0:
                        return 1
                    elif n < 0:
                        return 0
                    else:
                        # Number of partitions using a partition of size M
                        leftover = n - m
                        with_m = count_partitions(leftover, min(leftover, m))
                        # Number of partitions using size up to M-1
                        without_m = count_partitions(n, m-1)
                        return with_m + without_m
                

Variant call graph

140548255138000 count_partitions(2, 2) 140548255134320 count_partitions(6, 3) 140548255138528 count_partitions(0, 0) 140548255138000->140548255138528 (#2) 140548255138000->140548255138528:c 1 (#3) 140548255133792 count_partitions(2, 1) 140548255138000->140548255133792 (#4) 140548255138000->140548255133792:c 1 (#5) 140548255129776 count_partitions(3, 3) 140548255134320->140548255129776 (#8) 140548255134320->140548255129776:c 3 (#17) 140548255101520 count_partitions(6, 2) 140548255134320->140548255101520 (#18) 140548255134320->140548255101520:c 4 (#31) 140548792219360 count_partitions(0, 0) 140548255129776->140548792219360 (#9) 140548255129776->140548792219360:c 1 (#10) 140548792219888 count_partitions(3, 2) 140548255129776->140548792219888 (#11) 140548255129776->140548792219888:c 2 (#16) 140548793414128 count_partitions(4, 2) 140548255101520->140548793414128 (#19) 140548255101520->140548793414128:c 3 (#28) 140548255152304 count_partitions(6, 1) 140548255101520->140548255152304 (#29) 140548255101520->140548255152304:c 1 (#30) 140548792220416 count_partitions(1, 1) 140548792219888->140548792220416 (#12) 140548792219888->140548792220416:c 1 (#13) 140548275380304 count_partitions(3, 1) 140548792219888->140548275380304 (#14) 140548792219888->140548275380304:c 1 (#15) 140548275435392 count_partitions(2, 2) 140548793414128->140548275435392 (#20) 140548793414128->140548275435392:c 2 (#25) 140548255151776 count_partitions(4, 1) 140548793414128->140548255151776 (#26) 140548793414128->140548255151776:c 1 (#27) 140548792216672 count_partitions(0, 0) 140548275435392->140548792216672 (#21) 140548275435392->140548792216672:c 1 (#22) 140548255130304 count_partitions(2, 1) 140548275435392->140548255130304 (#23) 140548275435392->140548255130304:c 1 (#24) 140548257142464 count_partitions(6, 4) 140548257142464->140548255138000 (#1) 140548257142464->140548255138000:c 2 (#6) 140548257142464->140548255134320 (#7) 140548257142464->140548255134320:c 7 (#32) 99999999 Result 99999999->140548257142464:c 9 (#33)

Variant visualization

(6, 3) (2, 2) (6, 4) (2, 1) (0, 0) (2, 2) (3, 3) (6, 2) (6, 3) (0, 0) (3, 3) (3, 2) (3, 1) (1, 1) (3, 2) (6, 1) (4, 2) (6, 2) (4, 1) (2, 2) (4, 2) (2, 1) (0, 0) (2, 2)