Scribd
Upload
2 views12 pages

Recursion

The document discusses recursion in computer science, defining it as a structural and deferred process with phases of growing and shrinking stack behavior. It contrasts non-tail and tail recursion, explaining how tail recursion can be optimized into iteration, and highlights connections to discrete mathematics and algorithmic induction. Additionally, it covers applications of recursion in algorithms like perfect square detection and Fibonacci sequence calculation, emphasizing optimization techniques like memoization.

Uploaded by

Anand Kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views12 pages

Recursion

The document discusses recursion in computer science, defining it as a structural and deferred process with phases of growing and shrinking stack behavior. It contrasts non-tail and tail recursion, explaining how tail recursion can be optimized into iteration, and highlights connections to discrete mathematics and algorithmic induction. Additionally, it covers applications of recursion in algorithms like perfect square detection and Fibonacci sequence calculation, emphasizing optimization techniques like memoization.

Uploaded by

Anand Kumar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Definition Theorem

Recursion: Semantics, Stack Behaviour, and


Optimization

Laksmi Chowdary

Department of Computer Science


Gitam Universty

1 / 12
Recursion as a Structural Definition

Definition
For a ∈ R and b ∈ N,
(
1 b=0
power(a, b) =
a · power(a, b − 1) b > 0

This is a definition over the natural numbers using induction.

2 / 12
Recursion as a Deferred Process

Observation
Recursive computation builds expressions first, evaluation begins
only after reaching the base case.

power(2, 4) = 2(2(2(2(1))))

Two phases:
▶ Growing phase (stack expansion)
▶ Shrinking phase (stack unwinding)

3 / 12
Stack Evolution

Growing phase:

power(2, 4) → power(2, 3) → power(2, 2) → power(2, 1) → power(2, 0)

Shrinking phase:

1 → 2 → 4 → 8 → 16

LIFO discipline governs evaluation.

4 / 12
Non-Tail vs Tail Recursion

Definition (Non-Tail Recursion)


Recursive call is not the last operation.

f (n) = g(n) + f (n − 1)

Requires stack memory: O(n)

Definition (Tail Recursion)


Recursive call is the final operation.

f (n, acc) = f (n − 1, h(n, acc))

Can be optimized into iteration.


5 / 12
Recursion and Iteration

Theorem
Every tail-recursive function can be transformed into an equivalent
iterative process.

Tail Recursion ≈ Loop

Non-Tail Recursion ≈ Loop + Stack

Iteration executes. Recursion expresses structure.

6 / 12
Connection with Discrete Mathematics

▶ Recursive definitions correspond to mathematical induction


▶ Running time follows recurrence relations
▶ Example:
T (n) = T (n − 1) + c
T (n) = O(n)

Recursion is algorithmic induction.

7 / 12
Divide and Conquer: Perfect Square

Definition
An integer n is a perfect square iff

∃k ∈ N such that k 2 = n

Search space:
1≤k≤n
Using divide and conquer:
 
low + high
k=
2
Reduce search interval recursively.

8 / 12
Recursive Perfect Square Algorithm
def isPerfectSquare(n, low, high):
if low > high:
return False

mid = (low + high) // 2

if mid * mid == n:
return True
elif mid * mid < n:
return isPerfectSquare(n, mid+1, high)
else:
return isPerfectSquare(n, low, mid-1)

Recurrence:
T (n) = T (n/2) + c

T (n) = O(log n) 9 / 12
Dynamic Programming: Fibonacci


0
 n=0
F (n) = 1 n=1

F (n − 1) + F (n − 2) n>1

Naive recurrence:

T (n) = T (n − 1) + T (n − 2) + 1

T (n) = O(2n )

10 / 12
Optimization via Memoization

Store computed values:

Time = O(n)

Space = O(n)

Recursive structure + memory eliminates exponential


recomputation.

11 / 12
Conceptual Summary

▶ Recursion mirrors induction


▶ Stack enables deferred computation
▶ Tail recursion connects to iteration
▶ Divide and Conquer reduces logarithmically
▶ Dynamic Programming reduces exponential growth

12 / 12

You might also like