Scribd
Upload
63 views21 pages

Understanding Recursion Trees in Fibonacci

Recursion trees visualize the call structure of recursive functions. They showed that the Fibonacci recursive function calculates the same subproblems repeatedly, resulting in an exponential number of function calls as the problem size n increases. In contrast, a function that recursively calls itself on n/2 performs much fewer recursive calls, around 2n-1, due to the faster reduction of the problem size n/2 at each recursive call. This demonstrates how the rate at which a recursive problem size decreases impacts algorithm efficiency.

Uploaded by

Jorge Rodriguez
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
63 views21 pages

Understanding Recursion Trees in Fibonacci

Recursion trees visualize the call structure of recursive functions. They showed that the Fibonacci recursive function calculates the same subproblems repeatedly, resulting in an exponential number of function calls as the problem size n increases. In contrast, a function that recursively calls itself on n/2 performs much fewer recursive calls, around 2n-1, due to the faster reduction of the problem size n/2 at each recursive call. This demonstrates how the rate at which a recursive problem size decreases impacts algorithm efficiency.

Uploaded by

Jorge Rodriguez
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

Recursion Trees

Recursion Trees

• Visualize call structure

2
Recursion Trees

• Visualize call structure

• Example: fnc(8) unsigned int fnc (unsigned int n) {


...
return fnc(n/2) + fnc(n/2);
}

3
Fibonacci Tree Problem
Fibonacci - Recursion Tree
// POST: return value is the n-th
// Fibonacci number F(n)
ifmp::integer fib (const unsigned int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2); // n > 1
}

fib(4):

5
Fibonacci - Recursion Tree
// POST: return value is the n-th
// Fibonacci number F(n)
ifmp::integer fib (const unsigned int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2); // n > 1
}

fib(4):

1 1 0

1 0

6
Fibonacci - Recursion Tree

Fibonacci-number VS function calls


n=4:

fib(4):

1 1 0

1 0

7
Fibonacci - Recursion Tree

Fibonacci-number VS function calls


n=4: 3

fib(4):

1 1 0

1 0

8
Fibonacci - Recursion Tree

Fibonacci-number VS function calls


n=4: 3 9

fib(4):

1 1 0

1 0

9
Fibonacci - Recursion Tree

Fibonacci-number VS function calls


n=4: 3 9

fib(4):
Many more
function calls!

1 1 0

1 0

10
Fibonacci - Recursion Tree

Fibonacci-number VS function calls


Fibonacci growth:
n=4: 3 𝑛
9
fib(n) ~ 𝑐
(for 𝑛 large, c golden ratio)

n fib(n)
fib(4): 5
Many5more
10 55
function calls!
20 6’765

40 102’334’155

80 23’416’728’348’467’685

1 1 0

1 0

11
Fibonacci - Recursion Tree

Fibonacci-number VS function calls


Fibonacci growth:
n=4: 3 𝑛
9
fib(n) ~ 𝑐
(for 𝑛 large, c golden ratio)

n fib(n)
fib(4): 5
Many5more
10 55
function calls!
20 6’765

40 102’334’155

80 23’416’728’348’467’685
Requires
unbelievably 1 1 0
many recursive
1 0
calls!
12
The Problem

• Problem: Same computation multiple times

13
The Problem

• Problem: Same computation multiple times

1 1 0

1 0

14
The Problem

• Problem: Same computation multiple times


• Gets worse as n increases :-(

1 1 0

1 0

15
The Problem

• Not all recursive functions are this inefficient.

16
The Problem

• Not all recursive functions are this inefficient.

• Example: unsigned int fnc (unsigned int n) {


...
return fnc(n/2) + fnc(n/2);
}

17
The Problem

• Not all recursive functions are this inefficient.

• Example: unsigned int fnc (unsigned int n) {


...
2n - 1 return fnc(n/2) + fnc(n/2);
}

recursive calls in total

18
The Problem

• Not all recursive functions are this inefficient.


Number of Recursive Calls
• Example: n
unsigned int fnc (unsigned int n) {
fib... fnc
2n - 1 5
return fnc(n/2) + fnc(n/2);
> 5 9
}

recursive calls in total 10 > 55 19

20 > 6’765 39

40 > 102’334’155 79

80 > 23’416’728’348’467’685 159

19
The Problem

• Not all recursive functions are this inefficient.


Number of Recursive Calls
• Example: n
unsigned int fnc (unsigned int n) {
fib... fnc
2n - 1 5
return fnc(n/2) + fnc(n/2);
> 5 9
}

recursive calls in total 10 > 55 19

20 > 6’765 39

40 > 102’334’155 79

80 > 23’416’728’348’467’685 159

Mindblowing
difference!

20
The Problem

• Reason: 𝑛/2 falls much faster than 𝑛 − 1 and 𝑛 − 2


• 𝑛/2  sub-tree of height: log 2 (𝑛)
• 𝑛 − 1, 𝑛 − 2  sub-tree of height: 𝑛 − 1, 𝑛 − 2
log 2 8 = 3

21

You might also like