Recursion

ITEC 3160 Python Programming for Data Analysis,
Cengiz Günay

(License: CC BY-SA 4.0)

Prev - Errors and Exceptions, Next - Data structures and performance

(click to read more)

What is recursion

Reusing a function
Calling itself
Similar to a loop
But not linear, instead it could be exponential

Why recursion

What is the advantage over loops?

Divide-and-conquer type problems
Tree search
Sorting
Elegant solution

Limitations?

Less efficient
Can exhaust program stack

Designing a recursive algorithm

Do you have a nesting doll situation? Identify the part in your problem that repeats and when that happens.
Identify when the recursion ends. What is the condition that stops it?

Example: Factorial

$$f(n)=n!$$ $$f(n)=n\times{}(n-1)\times\cdots\times{}2\times{}1$$

What is the repeating part versus the termination condition?

Repeating pattern: each time multiply with one less number $$f(n)=n\times f(n-1)$$
Termination condition: we stop at 1 $$f(1)=1$$

Classic example: factorial

For demo purposes only, not today’s class activity.

Trees

A binary tree :

Always true in sorted binary tree (or binary search tree - BST) : $a<b<c$

Not a linear data structure, b is root node, b.left=a and b.right=c

class Node:
    def __init__(self, info): 
        self.info = info
        self.left = None
        self.right = None

Traversing trees without recursion

Can we write a non-recursive program to count all the nodes in tree?

Start with root node object (root.info=4), and you can go root.left or root.right to get to the next node. If there is no node, it will be an empty object (None).

Does it work for any tree?

With recursion

def node_count(node, count):
    if node.left:
        count = node_count(node.left, count + 1)
    if node.right:
        count = node_count(node.right, count + 1)
    return count

print(node_count(root, 1))