Recursion: Factorial and Fibonacci

CSC-211 · Semester III · Data Structures and Algorithms

beginner25 minAvailable

RecursionFunction call stack · divide & conquer

n =

active callreturnedwaiting

factorial(5)→ 120

└factorial(4)…

└factorial(3)…

└factorial(2)…

└factorial(1)…

Call stack depth (max)

0frames

Lab brief

Objective

Watch recursive calls unfold as a call tree, and relate the base case, recursive case and the return-value unwind.

Theory & concepts

A recursive function solves a problem by calling itself on a smaller instance. It needs a base case that stops the recursion and a recursive case that reduces the problem. The call tree visualizes this: each node is a call, its children are the recursive calls it makes, and the value of a node is computed only after its children return.

Rendering diagram…

Recursive call chain for factorial

fact(n):   n ≤ 1 → 1        else n × fact(n-1)
fib(n):    n ≤ 1 → n        else fib(n-1) + fib(n-2)
fact(4) = 4 × fact(3) = 4 × 3 × fact(2) = ... = 24

The stack connection

Each active call occupies a frame on the call stack. Deep recursion grows the stack; that is why an explicit stack (Unit 2) can replace recursion and why fib(n) re-computes fib(2) many times — the tree shows the redundant calls.

Prerequisites

Functions in any programming language
Basic sequence notation

Instructions

1Choose factorial or Fibonacci mode.
2Step through the preorder: each new node is a function call.
3Watch values appear bottom-up as children complete.
4Count how many times fib(2) is computed for fib(5).

Tasks

Trace fact(4)
Write the call chain and confirm the product 24.
Fibonacci redundancy
Count the duplicate fib(2) calls in the fib(5) tree.
Base case role
Remove the base case mentally and describe what happens.

Self-check

The call tree matches the hand-written expansion.
Base and recursive cases are correctly identified.
The student explains the redundancy of naive Fibonacci.

Environment

call treepreorder steppingreturn-value unwindmode presets