4. Stacks - Applications.data.structure.pdf

stack operation

1. Data
STRUCTURES
AND
ALGORITHMS
Stacks
Week 4

2. STACK
•Suppose you want to put these balls
on this tower.
2

3. STACK
•First, we put a red ball.
3

4. STACK
•Now, we put a green ball.
4

5. STACK
•Next, we put a black ball on top of it.
5

6. STACK
•At the end, we put the blue ball on top
of it.
6

7. STACK
•Now, please answer the following questions.
•Can we get the black ball before getting the blue
ball?
•Can we insert a new ball between green and red
ball?
•The answer to both of these questions is: NO
7

8. STACK
•It is because, there is only one way to remove
or insert a ball.
•We can insert any ball only at the top of other balls
(if any)
•We can remove only the topmost ball at a time.
•We have no direct access to any other balls, except
the one at the top.
•Such a list is called a “Stack”.
8

9. STACK
•In a stack, we have two operations:
•Push(X)
•Pop()
•Push(X) means to insert “X” at the top of the
stack.
•Pop() means to remove the topmost element
of the stack.
9

10. STACK
•In a stack, we have two operations:
•Push(X)
•Pop()
•Push(X) means to insert “X” at the top of the
stack.
•Pop() means to remove the topmost element
of the stack.
•If there is nothing in the stack, it is empty.
10

11. STACK
•Similarly, initially stack is empty.
11
⋮

12. STACK
•Similarly, initially stack is empty.
•After performing the following five operations,
the stack looks like this.
•Push(“First”)
•Push(“Second”)
•Push(“Third”)
•Push(“Fourth”)
•Push(“Last”)
12
⋮
Last
Fourth
Third
Second
First

13. STACK
•Now, we will perform the following operation.
•Pop()
13
⋮
Last
Fourth
Third
Second
First

14. STACK
•Now, we will perform the following operation.
•Pop()
•You will see that the “Last” element has been
popped out first.
•In other words, we can say that the behavior of
Stack is LIFO (Last in First out).
•In other words, FILO (First in Last out).
14
⋮
Fourth
Third
Second
First
Last

15. STACK
The stack is a simple data structure. We may have been using a stack
in our lives without even realizing it!
15

16. STACK ADT
•A stack is an Abstract Data Type (ADT), commonly used in
most programming languages.
•It is named stack as it behaves like a real-world stack.
•We can place or remove a card or plate from the top of the
stack only.
•At any given time, we can only access the top element of a
stack.
16

17. STACK ADT
17

18. Implementation
•A stack can be implemented by:
•Arrays
•Linked List
•In the first case, it will be of fixed size because arrays are basically
static.
•In the second case, stack will be of dynamic size.
•Each has its own merits & demerits.
18

19. Basic Operations on LIST ADT
•Push() To insert at the top of stack
•Pop() To access and remove the top of stack
•Peek() To access the top of stack without removal
•The stack will be full when its top reaches the maximum limit.
•The stack will be considered empty, if there is no element in the
stack.
19

20. Array Based Implementation ― Push()
Algorithm Push(value)
//MAX is the maximum size of Array (Stack)
If Top == MAX Then return FALSE
Top++
Stack[Top] = value
return TRUE
End Push
20

21. Push()
Algorithm Push(value)
//MAX is the maximum size of Array (Stack)
If Top == MAX Then return FALSE
Top++
Stack[Top] = value
return TRUE
End Push
21
Top
MAX = 5
Value = 10
5
4
3
2
1
0

22. Push()
Algorithm Push(value)
//MAX is the maximum size of Array (Stack)
If Top == MAX Then return FALSE
Top++
Stack[Top] = value
return TRUE
End Push
22
MAX = 5
Value = 10
5
4
3
2
1
0Top

23. Push()
Algorithm Push(value)
//MAX is the maximum size of Array (Stack)
If Top == MAX Then return FALSE
Top++
Stack[Top] = value
return TRUE
End Push
23
MAX = 5
Value = 10
5
4
3
2
1
0
Top

24. Push()
Algorithm Push(value)
//MAX is the maximum size of Array (Stack)
If Top == MAX Then return FALSE
Top++
Stack[Top] = value
return TRUE
End Push
24
10
MAX = 5
Value = 10
5
4
3
2
1
0
Top

25. Push()
Algorithm Push(value)
//MAX is the maximum size of Array (Stack)
If Top == MAX Then return FALSE
Top++
Stack[Top] = value
return TRUE
End Push
25
10
MAX = 5
Value = 10
5
4
3
2
1
0
Top

26. Push()
Algorithm Push(value)
//MAX is the maximum size of Array (Stack)
If Top == MAX Then return FALSE
Top++
Stack[Top] = value
return TRUE
End Push
26
12
11
-5
4
10
MAX = 5
Value = 5
5
4
3
2
1
0
Top

27. Push()
Algorithm Push(value)
//MAX is the maximum size of Array (Stack)
If Top == MAX Then return FALSE
Top++
Stack[Top] = value
return TRUE
End Push
27
12
11
-5
4
10
MAX = 5
Value = 5
5
4
3
2
1
0
Top

28. Array Based Implementation ― Pop()
Algorithm Pop()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
value = Stack[Top]
Top ― ―
return value
End Pop
28

29. Pop()
Algorithm Pop()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
value = Stack[Top]
Top ― ―
return value
End Pop
29
10Top
MAX = 5
5
4
3
2
1
0

30. Pop()
Algorithm Pop()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
value = Stack[Top]
Top ― ―
return value
End Pop
30
10Top
MAX = 5
5
4
3
2
1
0

31. Pop()
Algorithm Pop()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
value = Stack[Top]
Top ― ―
return value
End Pop
31
10Top
MAX = 5
5
4
3
2
1
0
value = 10

32. Pop()
Algorithm Pop()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
value = Stack[Top]
Top ― ―
return value
End Pop
32
10
Top
MAX = 5
5
4
3
2
1
0
value = 10

33. Pop()
Algorithm Pop()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
value = Stack[Top]
Top ― ―
return value
End Pop
33
10
Top
MAX = 5
5
4
3
2
1
0
value = 10

34. Pop()
Algorithm Pop()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
value = Stack[Top]
Top ― ―
return value
End Pop
34
10
Top
MAX = 5
5
4
3
2
1
0
value = 10
return 10

35. Pop()
Algorithm Pop()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
value = Stack[Top]
Top ― ―
return value
End Pop
35
Top
MAX = 5
5
4
3
2
1
0

36. Pop()
Algorithm Pop()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
value = Stack[Top]
Top ― ―
return value
End Pop
36
Top
MAX = 5
5
4
3
2
1
0
return NULL

37. Array Based Implementation ― Peek()
Algorithm Peek()
//MAX is the maximum size of Array (Stack)
If Top == 0 Then return NULL
return Stack[Top]
End Peek
37
5
2
-3
Top
5
4
3
2
1
0

38. Linked List Based Implementation ― Push()
Algorithm Push(value)
//Initially Position is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL

Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
38

39. Push()
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
39
0412
NULL
Head

40. Push()
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
40
0
4
12
NULL
Head

41. CASE I: Push( ) On top of a stack
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
41
0
4
12
NULL
Head
Value = 10
Size = 3

42. CASE I: Push()
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
42
0
4
12
NULL
Head
Value = 10
Size = 3
NewNode
NULL

43. CASE I: Push()
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
43
0
4
12
NULL
Head
Value = 10
Size = 3
10 NewNode
NULL

44. CASE I: Push()
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
44
0
4
12
NULL
Head
Value = 10
Size = 3
10 NewNode
NULL
FALSE

45. CASE I: Push()
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
45
0
4
12Head
Value = 10
Size = 3
10
NewNode
NULL

46. CASE I: Push()
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
46
0
4
12
Head
Value = 10
Size = 3
10
NewNode
NULL

47. CASE I: Push()
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
47
0
4
12
Head
Value = 10
Size = 4
10
NewNode
NULL

48. CASE I: Push( )
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
Head = N
N.next = NULL
Else
N.next = Head
Head = N
End If
Position++
return TRUE
End Push
48
0
4
12
Head
Value = 10
Size = 4
10
NewNode
NULL

49. CASE II: Push( ) In an Empty Stack
Algorithm Push(value) //Initially Size is 0, when stack is empty
If Size == MAX
return FALSE
Create New Node NewNode
NewNode.data = value
If Head == NULL
Head = NewNode
Else
Top.Up = NewNode
End If
Top = NewNode
Size++
return TRUE
End Push
49
Head
Top
Value = 20
Size = 0
NULL

50. CASEII: Push( )
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
N.next = NULL;
Else
N.next = Head;
End If
Head = N
Size++
return TRUE
End Push
50
Head
Value = 20
Size = 0
NULL

51. CASEII: Push( )
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
N.next = NULL;
Else
N.next = Head;
End If
Head = N
Size++
return TRUE
End Push
51
Head
Value = 20
Size = 0
NULL
NewNode

52. CASEII: Push( )
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
N.next = NULL;
Else
N.next = Head;
End If
Head = N
Size++
return TRUE
End Push
52
Head
Value = 20
Size = 0
NULL
20 NewNode

53. CASEII: Push( )
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
N.next = NULL;
Else
N.next = Head;
End If
Head = N
Size++
return TRUE
End Push
53
Head
Value = 20
Size = 0
NULL
20
NULL
NewNode
TRUE

54. Push()
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
N.next = NULL;
Else
N.next = Head;
End If
Head = N
Size++
return TRUE
End Push
54
Head
Value = 20
Size = 0
20
NULL
NewNode

55. CASEII: Push( )
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
N.next = NULL;
Else
N.next = Head;
End If
Head = N
Size++
return TRUE
End Push
55
Head
Value = 20
Size = 1
20
NULL
NewNode

56. CASEII: Push( )
Algorithm Push(value) //Initially Size is 0, when stack is empty
N = New Node
If N == NULL
return FALSE
N.data = value
If Head == NULL
N.next = NULL;
Else
N.next = Head;
End If
Head = N
Size++
return TRUE
End Push
56
Head
Value = 20
Size = 1
return TRUE
20
NULL
NewNode

57. Linked List Based Implementation ― Pop()
57
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

58. Pop()
58
Top
20
NULL
Size = 1
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

59. Pop()
59
Head
Top
20
NULL
Size = 1
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop
FALSE

60. Pop()
60
Top
20
NULL
Size = 1
value = 20Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

61. Pop()
61
Top
20
NULL
Size = 1
value = 20Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

62. Pop()
62
Top
NULL
Size = 1
value = 20Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

63. Pop()
63
Top
NULL
Size = 0
value = 20
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

64. Pop()
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop
64
Top
NULL
Size = 0
value = 20
return 20

65. Pop()
65
Size = 4
0
4
12Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

66. Pop()
66
Size = 4
0
4
12Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop
FALSE

67. Pop()
67
Size = 4
Value = 12
0
4
12Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

68. Pop()
68
Size = 4
Value = 12
0
4
12Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop
FALSE

69. Pop()
69
Size = 4
Value = 12
0
4
12Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

70. Pop()
70
Size = 4
Value = 12
0
4
12Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop
N

71. Pop()
71
Size = 4
Value = 12
0
4
12
Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop
N

72. Pop()
72
Size = 4
Value = 12
0
4
Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

73. Pop()
73
Size = 3
Value = 12
0
4
Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

74. Pop()
74
Size = 3
Value = 12
0
4
Top
10
NULL
Algorithm Pop( )
If Size == 0 Then return NULL
value = Top.data
If Size == 1
Delete Top
Top = NULL
Else
N == Top
Top = Top. Next
Delete N
End If
Size ― ―
return value
End Pop

75. Applications of Stack
•Stacks can be used for expression evaluation.
•Stacks can be used to check parenthesis matching in an expression.
•Stacks can be used forConversion from one form of expression to
another.
•Stacks can be used for Memory Management.
75

76. Applications of Stack
•Stack data structures are used in backtracking problems.
•Many compilers use a stack for parsing the syntax of expressions.
•Stack is used to reverse a string or any other array.
•Stack is used to keep information about the active functions or
subroutines.
•Keeping track of operations for managing the UNDO function.
76

77. Practice Question
•We have implemented a stack using arrays and singly linked list.
•Construct algorithms for basic stack operations if stack is
implemented using a doubly linked list.
77

78. Applications of Stack
•Stacks can be used for expression evaluation.
•Stacks can be used to check parenthesis matching in an expression.
•Stacks can be used forConversion from one form of expression to
another.
•Stacks can be used for Memory Management.
78

79. Applications of Stack
•Stack data structures are used in backtracking problems.
•Many compilers use a stack for parsing the syntax of expressions.
•Stack is used to reverse a string or any other array.
•Stack is used to keep information about the active functions or
subroutines.
•Keeping track of operations for managing the UNDO function.
79

80. The Call Stack
•Your computer uses a stack internally called the call stack. Let’s see it
in action. Here’s a simple function:
•This function greets you and then calls two other functions. Here are
those two functions:
80

81. The Call Stack
•Let’s walk through what happens when you call a function.
•Suppose you call greet(“maggie”).
•First, your computer allocates a box of memory for that function call.
81

82. The Call Stack
•Let’s walk through what happens when you call a function.
•Suppose you call greet(“maggie”).
•First, your computer allocates a box of memory for that function call.
•Now let’s use the memory.
•The variable name is set to “maggie”.
•That needs to be saved in memory.
82

83. The Call Stack
•Every time you make a function call, your computer
saves the values for all the variables for that call in
memory like this.
•Next, you print hello, maggie!
•Then you call greet2(“maggie”).
•Again, your computer allocates a box of memory
for this function call.
83

84. The Call Stack
•Your computer is using a stack for these
boxes.
•The second box is added on top of the first
one.
•You print how are you, maggie?
•Then you return from the function call.
•When this happens, the box on top of the
stack gets popped off.
84

85. The Call Stack
•Your computer is using a stack for these
boxes.
•The second box is added on top of the first
one.
•You print how are you, maggie?
•Then you return from the function call.
•When this happens, the box on top of the
stack gets popped off.
85

86. The Call Stack
•Now the topmost box on the stack is for the greet
function, which means you returned back to the greet
function.
•When you called the greet2 function, the greet
function was partially completed.
•This is the big idea behind this section: when you call a
function from another function, the calling function is paused
in a partially completed state.
•All the values of the variables for that function are still
stored in memory.
86

87. The Call Stack
•Now that you’re done with the greet2 function,
you’re back to the greet function, and you pick up
where you left off.
•First you print getting ready to say bye…. You call
the bye function.
•A box for that function is added to the top of the
stack.
87

88. The Call Stack
•Then you print ok bye! and return from the
function call.
•Bye function is popped out.
•And now you’re back to the greet function.
88

89. The Call Stack
•In greet function, there’s nothing else to be done
now.
•So, we will pop it too.
89

90. The Call Stack
•The stack is now empty.
•This stack, used to save the variables for multiple
functions, is called the call stack.
90

91. The Call Stack with Recursion
•Recursive functions use the call stack too!
•Let’s look at this in action with the factorial function.
•factorial(5) is written as 5!, and it’s defined like this:
5 * 4 * 3 * 2 * 1.
•Similarly, factorial(3) is:
3 * 2 * 1.
91

92. The Call Stack with Recursion
•Here’s a recursive function to calculate the factorial of a number:
•Now let’s call fact(3) and step through this call line by line and see
how the stack changes.
92

93. The Call Stack with Recursion
93

94. The Call Stack with Recursion
94

95. The Call Stack with Recursion
95

96. The Call Stack with Recursion
96

97. Example 5
97
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls

98. Example 5
98
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮

99. Example 5
99
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
A(3)

100. Example 5
100
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
A(2)
A(3)

101. Example 5
101
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
A(1)
A(2)
A(3)

102. Example 5
102
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
A(0)
A(1)
A(2)
A(3)

103. Example 5
103
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
A(1)
A(2)
A(3)

104. Example 5
104
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
A(2)
A(3)

105. Example 5
105
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
A(3)

106. Example 5
106
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮

107. Example 5
107
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
You can see that for an
Input of size n, we need
a stack of height n+1.

108. Example 5
108
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
If each block of stack
consists of k memory
locations, then total
space required is k(n+1)

109. Example 5
109
A( n )
{
If n >= 1
A(n-1);
//do something
}
A(3)
A(2)//do something
A(1) //do something
A(0) //do something
A(0) 1 call
A(1) 2 calls
A(2) 3 calls
A(3) 4 calls
⋮ ⋮
A(n) n+1 calls
⋮
S(n) = k(n+1) = O(n)

110. Example 6
110
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 call
A(1) 3 calls
A(2) 7 calls
A(3) 15 calls
⋮ ⋮
A(n) m calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)

111. Example 6
111
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
S(n) = k(2
n+1
-1) = O(2
n
)

112. Example 6
112
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮

113. Example 6
113
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2) 7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(3)

114. Example 6
114
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(2)
A(3)

115. Example 6
115
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(1)
A(2)
A(3)

116. Example 6
116
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0)
A(1)
A(2)
A(3)

117. Example 6
117
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0)
A(1)
A(2)
A(3)
1

118. Example 6
118
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0)
A(1)
A(2)
A(3)
1

119. Example 6
119
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0)
A(1)
A(2)
A(3)
1

120. Example 6
120
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0)
A(1)
A(2)
A(3)
12

121. Example 6
121
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0)
A(1) A(1)
A(2)
A(3)
12

122. Example 6
122
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0)
A(1) A(1)
A(2)
A(3)
12

123. Example 6
123
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0)
A(1) A(1)
A(2)
A(3)
121

124. Example 6
124
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(1) A(1)
A(2)
A(3)
121

125. Example 6
125
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(1) A(1)
A(2)
A(3)
121

126. Example 6
126
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(1) A(1)
A(2)
A(3)
121

127. Example 6
127
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(1) A(1)
A(2)
A(3)
1213

128. Example 6
128
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(1) A(1)
A(2) A(2)
A(3)
1213

129. Example 6
129
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(1) A(1) A(1)
A(2) A(2)
A(3)
1213

130. Example 6
130
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0)
A(1) A(1) A(1)
A(2) A(2)
A(3)
1213

131. Example 6
131
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0)
A(1) A(1) A(1)
A(2) A(2)
A(3)
12131

132. Example 6
132
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0)
A(1) A(1) A(1)
A(2) A(2)
A(3)
12131

133. Example 6
133
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0)
A(1) A(1) A(1)
A(2) A(2)
A(3)
12131

134. Example 6
134
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0)
A(1) A(1) A(1)
A(2) A(2)
A(3)
121312

135. Example 6
135
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0)
A(1) A(1) A(1) A(1)
A(2) A(2)
A(3)
121312

136. Example 6
136
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0) A(0)
A(1) A(1) A(1) A(1)
A(2) A(2)
A(3)
121312

137. Example 6
137
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0) A(0)
A(1) A(1) A(1) A(1)
A(2) A(2)
A(3)
1213121

138. Example 6
138
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0) A(0) A(0)
A(1) A(1) A(1) A(1)
A(2) A(2)
A(3)
1213121

139. Example 6
139
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0) A(0) A(0)
A(1) A(1) A(1) A(1)
A(2) A(2)
A(3)
1213121

140. Example 6
140
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0) A(0) A(0)
A(1) A(1) A(1) A(1)
A(2) A(2)
A(3)
1213121

141. Example 6
141
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0) A(0) A(0)
A(1) A(1) A(1) A(1)
A(2) A(2)
A(3)
1213121

142. Example 6
142
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
A(0) A(0) A(0) A(0)
A(0) A(0) A(0) A(0)
A(1) A(1) A(1) A(1)
A(2) A(2)
A(3)
1213121

143. Example 6
143
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2)7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
You can see that for an
Input of size n, we need
a stack of height n+1.

144. Example 6
144
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2) 7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
If each block of stack
consists of k memory
locations, then total
space required is k(n+1)

145. Example 6
145
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}
A(3)
A(2)P(3)
A(0) 1 = 2
0+1
― 1 call
A(1)3 = 2
1+1
― 1 calls
A(2) 7 = 2
2+1
― 1 calls
A(3)15 = 2
3+1
― 1 calls
⋮ ⋮
A(n)m = 2
n+1
― 1 calls
A(2)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
A(1)P(2)A(1)
A(0)P(1)A(0)A(0)P(1)A(0)
⋮
S(n) = k(n+1) = O(n)

146. Analyzing Time Complexity
T(n) = 2T(n-1) + c; n>=1
T(0) = c  This is the Anchor Condition
-------------------------------------------------------------------------
T(n) =2T(n-1)+c …eq(i)
T(n-1) =2T(n-1-1)+c
=2T(n-2)+c …eq(ii)
T(n-2) =2T(n-2-1)+c
=2T(n-3)+c …eq(iii)
146
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}

147. Analyzing Time Complexity
Putting eq(ii) in eq(i):
T(n) =2T(n-1)+c
=2[2T(n-2)+c] +c
=2
2
T(n-2)+2c+c …eq(iv)
Putting eq(iii) in eq(iv):
T(n) =2
2
[2T(n-3)+c]+2c+c
=2
3
T(n-3)+2
2
c+2c+c
Suppose we reach the anchor condition after k

calls:
T(n) =2
k
T(n-k)+2
k-1
c+…+2
2
c+2c+c ..eq(v)
147
T(n) =2T(n-1)+c …eq(i)
T(n-1)=2T(n-2)+c …eq(ii)
T(n-2)=2T(n-3)+c …eq(iii)
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}

148. Analyzing Time Complexity
As we know that T(0) will be the last recursive call, so
for what value of k will T(n-k) become T(0).
n-k=0  n=k
So eq(v) will become:
T(n) = 2
k
T(n-k)+2
k-1
c+…+2
2
c+2c+c
= 2
n
T(0)+2
n-1
c+…+2
2
c+2c+c
= 2
n
c+2
n-1
c+…+2
2
c+2c+c
= c(2
n
+2
n-1
+…+2
2
+2+1)
= c(2
n+1
― 1)
= O(2
n
)
148
A( n )
{
If n >= 1
A(n-1);
print n
A(n-1);
}

149. Converting
Infix to
Post-fix
Using Stack
149

150. Evaluation of
Post-fix
Using Stack

151. Infix to
Pre-fix using
Stack
151

152. Evaluation of
Pre-fix Using
Stack
152