Scribd
Upload
11 views13 pages

Understanding Recursion in Python

This document provides an overview of recursion in Python, explaining its basic structure, key components, and types, such as direct, indirect, tail, and non-tail recursion. It includes examples like factorial calculation and Fibonacci sequence to illustrate the concepts. Additionally, it compares recursion with iteration in terms of memory usage and problem complexity.

Uploaded by

khateeburrehman6627
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
11 views13 pages

Understanding Recursion in Python

This document provides an overview of recursion in Python, explaining its basic structure, key components, and types, such as direct, indirect, tail, and non-tail recursion. It includes examples like factorial calculation and Fibonacci sequence to illustrate the concepts. Additionally, it compares recursion with iteration in terms of memory usage and problem complexity.

Uploaded by

khateeburrehman6627
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 and Analyzing

Recursive Algorithms in Python


Lecture 7
Introduction to Recursion
• Recursion is when a function calls itself to solve smaller instances of the
same problem.
• Each recursive call simplifies the problem until a base case is reached.
• Useful for problems naturally defined in terms of smaller subproblems.
Basic Stucture:
def recursive_function(parameters):
if base_case_condition:
return base_result
else:
return recursive_function(modified_parameters)
Key Components of Recursion
1. Base Case : Stops recursion to avoid infinite calls.
2. Recursive Case : Defines how the problem is reduced.
Example of Recursion:
def factorial(n):
if n == 0: # base case
return 1
else: # recursive case
return n * factorial(n - 1)
print(factorial(6))
Base Case: When n == 0, recursion stops and returns 1.
Recursive Case: Multiplies n with the factorial of n-1 until it reaches the base
case.
Examples of Recursion
Factorial Calculation
Fibonacci Sequence
which represents the position in the sequence (for example, 1st, 2nd, 3rd number,
etc.).
Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Each number = sum of the two numbers before it. e.g 2 = 1 + 1 , 3 = 2 + 1, 5 = 3 +
2
Base Case1: If n == 1, the function returns 0, because the 1st Fibonacci number is
0.
Base Case2:If n == 2, the function returns 1, because the 2nd Fibonacci number is
1.
Recursive Case: If n is greater than 2, the function calls itself twice:
fibonacci(n-1) : previous number
fibonacci(n-2) :number before the previous one
Fibonacci Sequence
Types of Recursion
• Direct Recursion: Function calls itself directly.
• Indirect Recursion: Function A calls B, which calls A.
• Tail Recursion: Recursive call is the last statement in the function.
• Non-tail Recursion: Operations after recursive call.
1. Direct Recursion
A function calls itself directly.
2. Indirect Recursion
One function calls another function, and that
function calls the first function again.
3. Tail Recursion
The recursive call happens at the end, and there
is no work after the recursive call.
[Link]-Tail Recursion
• The recursive call happens first, and some
work is done after the call.
Recursion vs Iteration
• Recursion: Function calls itself. More memory, simpler for complex
problems.
• Iteration: Uses loops. Less memory, faster for simple problems.
Analyzing Recursive Algorithms
• Recursion is the process.
• A Recursive function is one that uses that process.

• The function hello() is recursive.


• The behavior of the function calling itself is recursion.

You might also like