Kodeclik Blog

About

Kodeclik is an online coding academy for kids and teens to learn real world programming. Kids are introduced to coding in a fun and exciting way and are challeged to higher levels with engaging, high quality content.

Popular Classes

Scratch Coding

Minecraft Coding

TinkerCAD

Roblox Studio

Python for Kids

Javascript for Kids

Pre-Algebra

Geometry for Kids

Copyright @ Kodeclik 2024. All rights reserved.

Recursion is a style of programming where a function calls itself one or more times repeatedly until a desired condition is met. Many classical algorithms in computer science are recursive in nature.

To understand recursion imagine we would like to write a function to print numbers from 1 to n. The usual, non-recursive, i.e., iterative way to write this function would be:

In recursion you would write it as:

Notice how in the definition of printer we call printer again! This is the essence of recursion, i.e. a function calling itself. Also note that when we call printer again recursively, we are calling it with a smaller argument, in this case (n-1). As recursive functions keep calling themselves, you need a base case to “stop” the recursion. That is taken care of by the “if” statement. In other words, the recursion stops when n reaches the value of 1.

To sum up the above function, if the input is 1, it just prints it and exits. If it is not 1, it calls it recursively with a smaller argument (n-1) and then prints (n). You can verify that it will print the same output as the non-recursive version.

Suppose we would like to reverse a list. It is easy to write this recursively. As done above, given a list you need to think about how to call the function again with a smaller list. Here is one possible solution:

This outputs:

This program’s logic works as follows. Given a list, we take away the first element by indexing it only from “1” (which is the second element). We then reverse the list from this point and add back the first element but at the end of the list (not the front, from where we took it). This addition at the end is done via the append function.

There are many other common functions that can be implemented with recursion. The factorial is a popular example.

This returns:

as expected.

Another example of recursion is the fibonacci function used to model growth of many natural phenomena:

This produces:

as expected.

Note that in the above program each invocation of the function potentially results in two recursive calls, not one as in the earlier examples.

Recursion leads to simpler code and easier to understand code. But it is certainly a style of programming that might not be natural to many programmers.

Recursion is natural for mathematical problems that are expressed in inductive notation and also for data structures like trees and graphs. In other words, the data structure itself is defined in a recursive manner and so traversing such data structures is naturally described using recursive notation.

Note that in all programs above there is a base case, i.e., the “if” case that is placed before the recursive call. If a suitable base case is not defined, the recursion will never stop and your program will run out of memory. For instance, let us try running the factorial program without the base case:

When you run this program, even though it begins with a small number, i.e., 10, the recursive calls keep decreasing the argument indefinitely and you will get an error such as:

What this means is that the Python interpreter needs to book-keep and remember the original invocation to return to after each recursive call and after some point the interpreter runs of memory for such book-keeping. This is an example of bad programming practice.

Recursion is just a programmatic way to express mathematical induction. If you can write functions by splitting them into a base case and an inductive step, you are well on your way to becoming a recursion expert!

Want to learn Python with us? Sign up for 1:1 or small group classes.

```
def printer(n):
for i in range(1,n+1):
print(i)
printer(10)
```

```
def printer(n):
if (n==1):
print(n)
else:
printer(n-1)
print(n)
printer(10)
```

```
def reverse(x):
if (x == []):
# if list is empty
# it is already reversed - return it!
return(x)
else:
# get everything except the first element
slist = x[1:]
# reverse it
reversed_slist = reverse(slist)
# append the first element to the reversed list
reversed_slist.append(x[0])
# return this as the answer
return(reversed_slist)
list = [1,2,3,4,5,6]
print(reverse(list))
```

`[6, 5, 4, 3, 2, 1]`

```
def factorial(n):
if (n==0):
return(1)
else:
return(n*factorial(n-1))
print(factorial(10))
```

`3628800`

```
def fib(n):
if (n==0):
return(0)
elif (n==1):
return(1)
else:
return(fib(n-1)+fib(n-2))
print(fib(6))
```

`8`

```
def factorial(n):
return(n*factorial(n-1))
print(factorial(10))
```

```
Traceback (most recent call last):
File "main.py", line 4, in <module>
print(factorial(10))
File "main.py", line 2, in factorial
return(n*factorial(n-1))
File "main.py", line 2, in factorial
return(n*factorial(n-1))
File "main.py", line 2, in factorial
return(n*factorial(n-1))
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
```