Tree Recursion

Tips for navigating the slides:
  • Press O or Escape for overview mode.
  • 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)
                    

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

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-2) + virfib(n-1)
                    

A tree-recursive process

4454057024 virfib(3) ret: 2 (#10) 4454084672 virfib(4) ret: 3 (#28) 4454057536 virfib(1) ret: 1 (#3) 4454057024->4454057536 2 (⇑1) 4454058048 virfib(2) ret: 1 (#9) 4454057024->4454058048 4 (⇑4) 4454085184 virfib(2) ret: 1 (#17) 4454084672->4454085184 12 (⇑8) 4454086720 virfib(3) ret: 2 (#27) 4454084672->4454086720 18 (⇑13) 4454058560 virfib(0) ret: 0 (#6) 4454058048->4454058560 5 (⇑2) 4454059072 virfib(1) ret: 1 (#8) 4454058048->4454059072 7 (⇑3) 4454085696 virfib(0) ret: 0 (#14) 4454085184->4454085696 13 (⇑6) 4454086208 virfib(1) ret: 1 (#16) 4454085184->4454086208 15 (⇑7) 4454087232 virfib(1) ret: 1 (#20) 4454086720->4454087232 19 (⇑9) 4454087744 virfib(2) ret: 1 (#26) 4454086720->4454087744 21 (⇑12) 4454096960 virfib(0) ret: 0 (#23) 4454087744->4454096960 22 (⇑10) 4454097472 virfib(1) ret: 1 (#25) 4454087744->4454097472 24 (⇑11) 4449338432 virfib(5) ret: 5 (#29) 4449338432->4454057024 1 (⇑5) 4449338432->4454084672 11 (⇑14)

Redundant computations

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

4536276032 virfib(3) ret: 2 4536303680 virfib(4) ret: 3 4536276544 virfib(1) ret: 1 4536276032->4536276544 2 (⇑1) 4536277056 virfib(2) ret: 1 4536276032->4536277056 3 (⇑4) 4536304192 virfib(2) ret: 1 4536303680->4536304192 7 (⇑8) 4536305728 virfib(3) ret: 2 4536303680->4536305728 10 (⇑13) 4536277568 virfib(0) ret: 0 4536277056->4536277568 4 (⇑2) 4536278080 virfib(1) ret: 1 4536277056->4536278080 5 (⇑3) 4536304704 virfib(0) ret: 0 4536304192->4536304704 8 (⇑6) 4536305216 virfib(1) ret: 1 4536304192->4536305216 9 (⇑7) 4536306240 virfib(1) ret: 1 4536305728->4536306240 11 (⇑9) 4536306752 virfib(2) ret: 1 4536305728->4536306752 12 (⇑12) 4536315968 virfib(0) ret: 0 4536306752->4536315968 13 (⇑10) 4536316480 virfib(1) ret: 1 4536306752->4536316480 14 (⇑11) 4531668032 virfib(5) ret: 5 4531668032->4536276032 1 (⇑5) 4531668032->4536303680 6 (⇑14) Screenshot of fib(4) diagram

(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)
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)

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)

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)

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
                            

Counting partitions process

4319065152 count_partitions(2,2) ret: 2 (#14) 4319093824 count_partitions(4,1) ret: 1 (#32) 4319065664 count_partitions(0,2) ret: 1 (#3) 4319065152->4319065664 2 (⇑1) 4319066176 count_partitions(2,1) ret: 1 (#13) 4319065152->4319066176 4 (⇑6) 4319094336 count_partitions(3,1) ret: 1 (#29) 4319093824->4319094336 16 (⇑14) 4319114816 count_partitions(4,0) ret: 0 (#31) 4319093824->4319114816 30 (⇑15) 4319066688 count_partitions(1,1) ret: 1 (#10) 4319066176->4319066688 5 (⇑4) 4319093312 count_partitions(2,0) ret: 0 (#12) 4319066176->4319093312 11 (⇑5) 4319067200 count_partitions(0,1) ret: 1 (#7) 4319066688->4319067200 6 (⇑2) 4319092800 count_partitions(1,0) ret: 0 (#9) 4319066688->4319092800 8 (⇑3) 4319094848 count_partitions(2,1) ret: 1 (#26) 4319094336->4319094848 17 (⇑12) 4319114304 count_partitions(3,0) ret: 0 (#28) 4319094336->4319114304 27 (⇑13) 4319095360 count_partitions(1,1) ret: 1 (#23) 4319094848->4319095360 18 (⇑10) 4319113792 count_partitions(2,0) ret: 0 (#25) 4319094848->4319113792 24 (⇑11) 4319095872 count_partitions(0,1) ret: 1 (#20) 4319095360->4319095872 19 (⇑8) 4319113280 count_partitions(1,0) ret: 0 (#22) 4319095360->4319113280 21 (⇑9) 4314457152 count_partitions(4,2) ret: 3 (#33) 4314457152->4319065152 1 (⇑7) 4314457152->4319093824 15 (⇑16)