Data Structures and Algorithms in Python | 18. Recursion by Abraham | Learn Smarter
K12 Students

Academics

AI-Powered learning for Grades 8–12, aligned with major Indian and international curricula.

Academics

Grades

Grade 8 Grade 9 Grade 10 Grade 11 Grade 12

Curriculum

CBSE ICSE IB
Professionals

Professional Courses

Industry-relevant training in Business, Technology, and Design to help professionals and graduates upskill for real-world careers.

Professional Courses
Games

Interactive Games

Fun, engaging games to boost memory, math fluency, typing speed, and English skills—perfect for learners of all ages.

games
Typing
Memory
Math
English Adventures
Knowledge
18. Recursion

Recursive functions utilize inductive definitions, as seen in the factorial function and Fibonacci series. This chapter explores how inductive reasoning leads to recursive implementations in Python, examining list structures and sorting algorithms like insertion sort. The relationship between recursion and efficiency is also discussed, highlighting practical challenges such as the recursion limit in Python and the need for robust algorithms for larger datasets.

Sections

  • 18

    Recursion

    This section introduces the concept of recursion in programming, explaining how recursive functions are defined inductively and providing examples.

    Learning Practice

  • 18.1.1

    Inductive Definitions

    Inductive definitions form the foundation for recursive functions in programming, exemplified by functions such as factorial, multiplication, and Fibonacci.

    Learning Practice

  • 18.1.2

    Factorial Function

    The section discusses the factorial function as an example of recursive functions, emphasizing its inductive definition and implementation in Python.

    Learning Practice

  • 18.1.3

    Multiplication As Repeated Addition

    This section introduces multiplication through the concept of repeated addition, detailing inductive and recursive definitions in programming.

    Learning Practice

  • 18.1.4

    Fibonacci Series

    This section introduces the Fibonacci series and its recursive definition, illustrating how it can be computed using inductive reasoning.

    Learning Practice

  • 18.1.5

    Inductive Definition And Recursive Computation

    This section explores the concepts of inductive definitions and recursive functions, highlighting examples like factorial, multiplication, Fibonacci series, and list operations.

    Learning Practice

  • 18.1.6

    Inductive Structures Like Lists

    This section discusses the concept of inductive structures, particularly how they are used in defining recursive functions such as factorials, multiplication, and list operations.

    Learning Practice

  • 18.1.7

    Computing The Length Of A List

    This section discusses how to compute the length of a list using inductive definitions and recursive functions.

    Learning Practice

  • 18.1.8

    Summing Elements Of A List

    This section covers the concept of recursive functions and their application in summing elements of a list using inductive definitions.

    Learning Practice

  • 18.1.9

    Insertion Sort

    Insertion sort is a simple sorting algorithm that builds a sorted array one element at a time and is based on inductive reasoning.

    Learning Practice

  • 18.1.10

    Recursive Definition Of Insertion Sort

    This section covers the recursive definition of the insertion sort algorithm, explaining its foundation via inductive reasoning and recursion.

    Learning Practice

  • 18.1.11

    Recursion Limit In Python

    This section discusses recursive functions in Python, specifically focusing on the recursion limit and how it affects programming.

    Learning Practice

  • 18.1.12

    Analysing Complexity Of Recursive Insertion Sort

    This section discusses the recursive nature of insertion sort, its implementation in Python, and the analysis of its time complexity.

    Learning Practice

  • 18.1.13

    Comparison Of Sorting Algorithms

    This section explores recursive functions and introduces sorting algorithms, particularly focusing on insertion sort and its efficiency compared to selection sort.

    Learning Practice

  • 18.1.14

    Next Week's Topic

    This section discusses recursive functions, their definitions, examples, and their relation to data structures like lists.

    Learning Practice

References

Chapter 18.pdf

Class Notes

Memorization

What we have learnt

  • Recursive functions are def...
  • Inductive definitions allow...
  • Python imposes a recursion ...

Final Test

Revision Tests