Recursion is a programming technique where a function calls itself to solve a problem or execute a task.

What does recursion use instead of iterative loops?

The idea of self-reference , to break down complicated problems into more manageable subproblems.

Name the three features of a recursive algorithm.

The function must call itself , there must be a base case , and there must be a stopping base that is reachable after a finite number of times.

A condition where the function can return a value without further recursive calls .

Recursive programs must reach the base case in a number of steps.

Recursive programs must reach the base case in a finite number of steps.

How does a recursive function progress towards the base case?

It calls itself with a modified input parameter , breaking the problem into smaller instances each time.

What is the base case for factorial(n) ?

When n is 0 or 1 , the function returns 1 .

What does factorial(5) return?

120 , since 5! = 5 x 4 x 3 x 2 x 1.

What happens without a proper stopping condition?

The function calls itself indefinitely , using up excessive memory and causing stack overflow errors and program crashes.

How do you design a stopping condition?

Identify the simplest scenario where the function can give a direct result , and define that as the base case.

Name two benefits of recursion.

It is concise , especially for structures like trees or fractals, and simple to read and maintain because it states what needs doing rather than how.

Name three drawbacks of recursion.

Performance , because repeated function calls are CPU and memory intensive; debugging , because the program state is harder to track; and limited application , because not all problems suit recursion.

True or False? Recursion always performs better than iteration.

False. Iteration is more efficient and uses less memory . Repeated recursive calls are CPU and memory intensive, leading to slower execution.

Name three benefits of iteration.

Better performance with less memory usage, easier to understand and debug , and wider application to a range of problems.

Name two drawbacks of iteration.

It can become very complex and use more lines of code than a recursive alternative, and it is less concise .

In the countdown example, what replaces the recursive call in the iterative version?

A while loop that checks n > 0 .

What are the two advantages of the iterative countdown?

Less memory is used , giving increased performance, and it is easier to debug .

How does the compiler treat a recursive function?

Not like a loop. It uses the call stack to keep track of each function call.

Each time a function calls itself, the system stores a snapshot on the stack.

Each time a function calls itself, the system stores a snapshot on the call stack.

The snapshot of a single function call stored on the call stack.

Name the three things a stack frame contains.

The function name , the value of parameters and variables at that level, and the place to return to when the function finishes.

When do calls stop being added to the stack?

When the base case is reached .

Define stack unwinding .

The process of returning values back up the stack after the base case has been reached.

What happens during unwinding?

The most recent call completes and returns a value , control goes back to the previous stack frame , and this continues until the original call receives the final result.

Trace factorial(3) down the call stack.

factorial(3) calls 3 * factorial(2) ; factorial(2) calls 2 * factorial(1) ; factorial(1) hits the base case and returns 1 .

What does the unwinding of factorial(3) give?

factorial(2) = 2 x 1 = 2 , then factorial(3) = 3 x 2 = 6 .

What was on the stack at the deepest point of factorial(3) ?

factorial(3) , factorial(2) and factorial(1) , each popped off as the return values passed back up.

Define stack overflow .

What happens when recursive calls never stop , exhausting the available memory.

True or False? A recursive function without a base case simply returns nothing.

False. The stack never stops growing , which leads to a stack overflow and causes the program to crash.

A LevelComputer ScienceCambridge (CIE)Flashcards19. Computational thinking & Problem-solvingRecursion

Recursion (Cambridge (CIE) A Level Computer Science): Flashcards

Exam code: 9618

1/29

0Still learning

Know0

FrontRecursion
Define recursion.

Was this flashcard helpful?

Cards in this collection (29)

Define recursion.
Recursion is a programming technique where a function calls itself to solve a problem or execute a task.
What does recursion use instead of iterative loops?
The idea of self-reference, to break down complicated problems into more manageable subproblems.
Name the three features of a recursive algorithm.
The function must call itself, there must be a base case, and there must be a stopping base that is reachable after a finite number of times.
Define base case.
A condition where the function can return a value without further recursive calls.
Recursive programs must reach the base case in a number of steps.
Recursive programs must reach the base case in a finite number of steps.
How does a recursive function progress towards the base case?
It calls itself with a modified input parameter, breaking the problem into smaller instances each time.
What is the base case for factorial(n)?
When n is 0 or 1, the function returns 1.
What does factorial(5) return?
120, since 5! = 5 x 4 x 3 x 2 x 1.
What happens without a proper stopping condition?
The function calls itself indefinitely, using up excessive memory and causing stack overflow errors and program crashes.
How do you design a stopping condition?
Identify the simplest scenario where the function can give a direct result, and define that as the base case.
Name two benefits of recursion.
It is concise, especially for structures like trees or fractals, and simple to read and maintain because it states what needs doing rather than how.
Name three drawbacks of recursion.
Performance, because repeated function calls are CPU and memory intensive; debugging, because the program state is harder to track; and limited application, because not all problems suit recursion.
True or False?
Recursion always performs better than iteration.
False.
Iteration is more efficient and uses less memory. Repeated recursive calls are CPU and memory intensive, leading to slower execution.
Name three benefits of iteration.
Better performance with less memory usage, easier to understand and debug, and wider application to a range of problems.
Name two drawbacks of iteration.
It can become very complex and use more lines of code than a recursive alternative, and it is less concise.
In the countdown example, what replaces the recursive call in the iterative version?
A while loop that checks n > 0.
What are the two advantages of the iterative countdown?
Less memory is used, giving increased performance, and it is easier to debug.
How does the compiler treat a recursive function?
Not like a loop. It uses the call stack to keep track of each function call.
Each time a function calls itself, the system stores a snapshot on the stack.
Each time a function calls itself, the system stores a snapshot on the call stack.
Define stack frame.
The snapshot of a single function call stored on the call stack.
Name the three things a stack frame contains.
The function name, the value of parameters and variables at that level, and the place to return to when the function finishes.
When do calls stop being added to the stack?
When the base case is reached.
Define stack unwinding.
The process of returning values back up the stack after the base case has been reached.
What happens during unwinding?
The most recent call completes and returns a value, control goes back to the previous stack frame, and this continues until the original call receives the final result.
Trace factorial(3) down the call stack.
factorial(3) calls 3 * factorial(2); factorial(2) calls 2 * factorial(1); factorial(1) hits the base case and returns 1.
What does the unwinding of factorial(3) give?
factorial(2) = 2 x 1 = 2, then factorial(3) = 3 x 2 = 6.
What was on the stack at the deepest point of factorial(3)?
factorial(3), factorial(2) and factorial(1), each popped off as the return values passed back up.
Define stack overflow.
What happens when recursive calls never stop, exhausting the available memory.
True or False?
A recursive function without a base case simply returns nothing.
False.
The stack never stops growing, which leads to a stack overflow and causes the program to crash.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:AlgorithmsNext:Programming Paradigms