- Transition to Processing
- Primitive Operations
- Algorithms
- Variables
- Debugging in Processing
- Conditions
- Loops
- Functions
- Scope
- Compound Data
- Reference Semantics
- Refactoring
- Transition to Java
- Debugging in Java
- Unit Testing
- Classes - Writing your own Types
- Classes - Functions inside objects
- Recursion
- Lists
- Iteration
- Recursive Lists
- Searching

- Logic and Proofs
- Relations
- Mathematical Functions
- Matrices
- Binary Numbers
- Trigonomtry
- Finite State Machines
- Turing Machines
- Counting - Inclusion/Exclusion
- Graph Algorithms

- Algorithm Efficiency
- Algorithm Correctness
- Trees
- Heaps, Stack, and Queues
- Maps and Hashtables
- Graphs and Graph Algorithms
- Advanced Trees and Computability

- Command line control
- Transition to C
- Pointers
- Memory Allocation
- IO
- Number representations
- Assembly Programming
- Structs and Unions
- How memory works
- Virtual Memory

- Version Control with Git
- Inheritance and Overloading
- Generics
- Exceptions
- Lambda Expressions
- Design Patterns
- Concepts of Concurrency
- Concurrency: Object Locks
- Modern Concurrency

- System Models
- Naming and Distributed File Systems
- Synchronisation and Concurrency
- Fault Tolerance and Security
- Clusters and Grids
- Virtualisation
- Data Centers
- Mobile Computing

- Transition to Scala
- Functional Programming
- Syntax Analysis
- Name Analysis
- Type Analysis
- Transformation and Compilation
- Control Abstraction
- Implementing Data Abstraction
- Language Runtimes

- Transition to Coq
- Proof by Induction, Structured Data
- Polymorphism and Higher-Order Functions
- More Basic Tactics
- Logical Reasoning in Proof Assistants
- Inductive Propositions
- Maps
- An Imperative Programming Language
- Program Equivalence
- Hoare Logic
- Small-Step Operational Semantics
- Simply-typed Lambda Calculus

- Recognise difference between iterative and recursive code
- Be able to trace recursive functions and methods
- Be able to write recursive functions and methods

There are two classical approaches to solving algorthmic problems:

- Iterative
- Recursive

The distinctive property of *iterative* solutions is that they do not reduce a problem to a simpler form of itself.

Add all integers between `low`

and `high`

(inclusive on both sides, and assuming `low`

<= `high`

), I can go through each integer and add it to an accumulating variable, say `total`

.

1
2
3
4
5
6
7

public static int sum(int low, int high) {
int total = 0;
for(int i=low; i<=high; i++) {
total = total + i;
}
return total;
}

The distinctive property of *recursive* solutions is that they reduce a problem to a simpler form of itself.

For the same problem statement used for iterative solutions, we can say that the sum of all integers from `low`

to `high`

is:

1
2
3
4
5

if low <= high:
sub = sum of all integers from (low+1) to high
return (low + sub)
else
return 0

Focus on the part

1 sum of all integers from `low+1` to `high`

It is the same problem as the original problem, except there is one less number to handle, and thus is *simpler*.

It has been proven that there is a recursive solution for every iterative solution and vice versa. We will soon look at some of the aspects to consider while deciding on which approach to take.

Some solutions have an intuitive recursive design. Some examples (we assume n >= 0 for all examples):

- x to the power of n:
`x`

^{n}=`x`

^{n-1}*`x`

if n > 0`x`

^{0}= 1

- number of digits in an integer:
`nDigits(n)`

=`nDigits(n/10) + 1`

if n > 0`nDigits(0)`

= 0

- sum of the first n positive integers (1 + 2 + … + n):
`sum(n) = sum(n-1) + n`

if n > 0`sum(0)`

= 0

While trivial problems have fairly obvious recursive **and** iterative solutions, it’s much easier to find a recursive solution to the more complex problems. For example, creating a random permutation of the word “super”.

random permutation of the word “super” = random character from “super” (say ‘u’) + random permutation of the word “sper”

random permutation of the word “sper” = random character from “sper” (say ‘r’) + random permutation of the word “spe”

random permutation of the word “spe” = random character from “spe” (say ‘s’) + random permutation of the word “pe”

random permutation of the word “pe” = random character from “pe” (say ‘e’) + random permutation of the word “p”

random permutation of the word “p” = random character from “p” (has to be ‘p’) + random permutation of the word “”

random permutation of the word “” = “” (end case)

Plugging the values back:

random permutation of the word “p” = ‘p’ + “” = “p”

random permutation of the word “pe” = ‘e’ + “p” = “ep”

random permutation of the word “spe” = ‘s’ + “ep” = “sep”

random permutation of the word “sper” = ‘r’ + “sep” = “rsep”

random permutation of the word “super” = ‘u’ + “rsep” = “ursep”

Advanced data structures (such as linked lists, trees and graphs) are recursive in nature and it is logical to operate recursively on them.

- Each method call requires:
- Variables associated with that call to be stored in the memory, thereby requiring more memory.
- Caller to transfer the control to the method called (callee), and then the callee to execeute and return control, possible with a value, back to the caller, thus adding to processing time. Hence, recursive solutions are generally have a little processing time overhead.

We will see concrete examples of this once we talk about recursive implementation.

Before we jump into a method calling itself, it’s important to understand what happens when a method is called. Consider the following example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static void main(String[] args) {
int c = 1729;
int d = foo(c);
System.out.println(d);
}
public static int foo(int a) {
int temp = bar(a);
int result = temp * temp;
return result;
}
public static int bar(int b) {
int answer = b % 10;
return answer;
}

Method call is placed on the stack. Note that parameter is `null`

because we typically do not pass any arguments to main, at least in this unit.<p>

`foo`

with parameter `c`

Another entry is made for the call to `foo`

and placed on the stack.<p>

`foo`

calls `bar`

with parameter `a`

A third entry is made for the call to `bar`

and placed on the stack.<p>

`bar`

returns value to `foo`

Entry for `bar`

is taken off the stack. `foo`

becomes the active method.<p>

`foo`

returns value to `main`

Entry for `foo`

is taken off the stack. `main`

becomes the active method.<p>

## STEP 6: Rest of main executes

Each method expects zero or more values and gives the passed values some name. These are called *formal parameters*.

When the method is called, appropriate type of values (hopefully) are passed to it. These are called *actual parameters*.

Consider the following example:

1
2
3
4

public static int foo(int a) {
int b = a*a;
return b;
}

In the above example, `a`

is the name of the formal parameter in method `foo`

. Whenever, `foo`

is called with a value of the right type (int), it (the passed value) is copied into variable `a`

that stays in memory during the current execution of `foo`

.

Here,

`a`

is theformal parameter.

Now let’s say the client code is:

1
2
3
4
5

public static void main(String[] args) {
int p = 10;
int q = foo(p);
System.out.println(q);
}

The variable `p`

is being passed as a parameter to method `foo`

. Java checks it’s of the right type (`int`

) and copies it into variable `a`

during the execution of `foo(p)`

.

Here,

`p`

is theactual parameter.

Now consider a different client code:

1
2
3
4
5

public static void main(String[] args) {
int a = 10;
int result = foo(a);
System.out.println(a);
}

Now we have a variable `a`

in method main (represented by `main: a`

) being passed to `foo`

and copied into variable `a`

, represented by `foo(10): a`

. This is ok since the two variables, although with the same name, exist in different scopes. The following figure summarizes the transaction.

When a method calls itself, another entry is added to the top of the method stack.

Consider the following code:

1
2
3

public static void foo() {
foo();
}

This is the most basic recursive example, where the method `foo`

calls itself, placing another instance on top of the stack.

Of course, since this process never terminates, the stack keeps growing infinitely. As you might imagine, there is a limit to the number of entries in the method stack and when this is reached, we get `StackOverflowError`

.

Thus, our job is to ensure that methods don’t call themselves infinitely.

Consider the following code:

1
2
3
4
5
6
7
8
9
10

public static void main(String[] args) {
int n = 4;
foo(n);
}
public static void foo(int n) {
System.out.println(n);
int m = n-1;
foo(m);
}

The output you will get before finally getting a `StackOverflowError`

is:

1
2
3
4
5
6
7
8
9
10

4
3
2
1
0
-1
-2
-3
-4
and on and on and on ...

An illustration of memory transactions is given below

… and it repeats forever (ends with `StackOverflowError`

)

It is critical that we have an *end case* of a *terminal case*.

1
2
3
4
5
6
7

public static void foo(int n) {
if(n >= 1) {
System.out.println(n);
int m = n-1;
foo(m);
}
}

In the above modified method, we have enclosed the entire code in a conditional block. As soon as `n`

drops below 1, it’s effectively an empty method body and it returns the control back to the caller.

1
2
3
4
5
6
7
8
9
10

main(null) calls foo(4)
foo(4) displays 4 and calls foo(3)
foo(3) displays 3 and calls foo(2)
foo(2) displays 2 and calls foo(1)
foo(1) displays 1 and calls foo(0)
foo(0) does nothing and returns control to foo(1)
foo(1) returns control to foo(2)
foo(2) returns control to foo(3)
foo(3) returns control to foo(4)
foo(4) returns control to main(null)

The output you get is:

1
2
3
4

4
3
2
1

Following are two different ways of handling the terminal case:

1
2
3
4
5
6
7
8

public static int sum(int n) {
if(n >= 1) {
return n + sum(n-1);
}
else {
return 0;
}
}

1
2
3
4
5
6

public static int sum(int n) {
if(n >= 1) {
return n + sum(n-1);
}
return 0;
}

1
2
3
4
5
6
7
8

public static int sum(int n) {
if(n < 1) {
return 0;
}
else {
return n + sum(n-1);
}
}

1
2
3
4
5
6

public static int sum(int n) {
if(n < 1) {
return 0;
}
return n + sum(n-1);
}

Define a method that when passed an integer, returns the sum of all integers from 1 to that integer.

Examples:

Input = 4 -> return 1 + 2 + 3 + 4 (10)

Input = 6 -> return 1 + 2 + 3 + 4 + 5 + 6 (21)

Let’s call the method `sum`

and the the formal parameter `n`

sum(n) = 1 + 2 + … + (n-1) + n

can be written as:

sum(n) = [1 + 2 + … + (n-1)] + n

But

[1 + 2 + … + (n-1)] is sum(3)

(by the problem statement)

Hence,

sum(n) = sum(n-1) + n

1
2
3

public static int sum(int n) {
return sum(n-1) + n;
}

But this version will result in the method calling itself indefinitely, until JVM causes `StackOverflowError`

.

We need to address the end case:

sum(0) = 0

1
2
3
4
5
6
7

public static int sum(int n) {
if(n == 0) {
return 0;
}
//control reaches here only if n is not 0
return sum(n-1) + n;
}

What happens if the client, maliciously, calls the method with parameter -3?

`sum(-3)`

-> `sum(-4)`

-> `sum(-5)`

…

Since the parameter is never equal to 0, the method, when initially called with a negative value, calls itself indefinitely.

Eventually JVM causes `StackOverflowError`

.

1
2
3
4
5
6
7

public static int sum(int n) {
if(n <= 0) { //return 0 for anything less than 1
return 0;
}
//control reaches here only if n is more than 0
return sum(n-1) + n;
}

1

sum(4) = sum(3) + 4

1

sum(3) = sum(2) + 3

1

sum(2) = sum(1) + 2

1

sum(1) = sum(0) + 1

1

sum(0) returns 0 (terminal case)

1

sum(1) returns 0 + 1 (1)

1

sum(2) returns 1 + 2 (3)

1

sum(3) returns 3 + 3 (6)

1

sum(4) returns 6 + 4 (10)

1
2
3
4
5
6
7
8
9
10
11

main(null) calls sum(4)
sum(4) calls sum(3)
sum(3) calls sum(2)
sum(2) calls sum(1)
sum(1) calls sum(0)
sum(0) returns 0 to sum(1)
sum(1) adds 1 to the received value (0) and returns 1 to sum(2)
sum(2) adds 2 to the received value (1) and returns 3 to sum(3)
sum(3) adds 3 to the received value (3) and returns 6 to sum(4)
sum(4) adds 4 to the received value (6) and returns 10 to main()
main(null) uses the received value (10) as needed