Recursive and lambda functions

This is a continuation of exercise 12 b (A function that returns a value)

Recursive functions

We have discussed how to create a function, how to pass an argument to a function and then how to call a function. We have done a lot. It will pay us well if we take breaks frequently.

Kindly take a break to revise what we learnt so far and also take a long break away from PC.

In this exercise, we would discuss more on function. A recursive function calls itself. It does so until the base case becomes false.

Let's implement a factorial function. Our function will take in an integer input. If the input is less than 1, the function returns 1, else we proceed.

Let the integer input be, n. n factorial is, n! = n * (n - 1) * (n - 2) * (n - 3) * ... * 1. Our base case is 1. When we get to 1, we break or terminate the recursive function.

Example 1 - For loop

factorial = 1
n = int(input("Enter n: "))

if n < 1:
    print(1)
else:
    for i in range(1, n+1):
        factorial *= i

    print(factorial)

# input  output
#    3     6
#    5     720
#    15    1307674368000

Example 2 - Function

Now we shall implement the above using a recursive function.

def factorial(n):
    if n < 1:
        return 1

    else:
        return n * factorial(n-1)

def factorial(n): we define a function called factorial that take an integer argument, n.
if n < 1: return 1: we check the base case and return 1. The function returns 1 and the execution stops.
else: return n * factorial(n-1): if n > 1, we return n multiplied by factorial(n-1).
If n=5, we would have that:
- factorial(5) = 5 * factorial(4)
- factorial(5) = 5 * 4 * factorial(3)
- factorial(5) = 5 * 4 * 3 * factorial(2)
- factorial(5) = 5 * 4 * 3 * 2 * factorial(1)
- factorial(5) = 5 * 4 * 3 * 2 * 1
- factorial(5) = 720

Example 3

Implementation of Euclid GCD algorithm. We are interested in the greatest common divisor of two numbers, gcd(a, b).

Algorithm:

let a, b be the two numbers
let r be the remainder of a and b, a % b
check if r is 0, b divides a, if so, return b
else assign b to a and r to b and repeat the second step

a = int(input("Enter a: "))
b = int(input("Enter b: "))

while True:
    r = a % b

    if r == 0:
        print(b)
        break

    else:
        a = b
        b = r

# a = 72
# b = 96
# gcd(a, b) = 24

Example 4

Using recursion.

def gcd(a, b):
    r = a % b

    if r == 0:
        return b

    else:
        return gcd(b, r)

print(gcd(72, 96))  # 24

Let us shorten this code

def gcd(a, b):
    if a % b == 0:
        return b

    return gcd(b, a % b)

Lambda functions

Lambda function is also known as anonymous function - a function without a name. We can say it is a one-time-function. We create a lambda function using the lambda keyword. Simply, (lambda comma-separated-args: body)

Structure

Let's consider a function that increments a given integer by one and returns the value.

def inc(n):
    return n + 1


print(inc(2))  # 3

The snippet above uses the def keyword to create the function. Now let's see how we would use the lambda keyword to create the same function.

Example 5

print((lambda x: x+1)(2))  # 3

So the structure of a lambda function is similar to that of normal function. We use the lambda keyword instead of def, the function has no name. Any parameters are space comma-separated from the lambda keyword. The function body is separated by a colon, :.

From example 5, we passed the argument, 2, to the lambda function. Notice how it was passed.

Example 6

We can pass multiple arguments into a lambda function. Note that we can not use return lambda function. Let's use a lambda function to compare two numbers and return the lesser number.

print((lambda a, b: a if a < b else b)(2, 4))  # 2

Normally we would have written,

def min_val(a, b): return a if a < b else b


print(min_val(2, 4))  # 2

This is the same as :

def min_val(a, b):
    if a < b:
        return a
    else:  #  we can comment out the else:
        return b

We can assign a name to a lambda function

Consider example 5 where we increment a given number by one, we can pass the lambda function to a variable and call the variable like a function later.

inc = (lambda n: n + 1)

print(inc(2))  # 3

Can you tell the difference between these two snippets below?

# first func
inc = (lambda x: x + 1)
print(inc(4))

# second func
inc = (lambda x: x + 1)(4)
print(inc)

In the first func, the lambda function was assigned to inc. inc was called and an argument of value, 4 was passed. So we can say that inc is a function.
In the second func, an argument of value 4 was passed to the lambda function. The result was assigned to inc. So inc is just another variable of value, 4 + 1 = 5 and not a function.

Practicals

Write a function to sort this list, [[47, 3, 1, 34], [0. - 3, 4], [7, 21, 13, 37, 8]]
Write a function that returns the temperature from degree Fahrenheit to degree Celsius
Write a function that returns the sum of numbers between a given range inclusive. If the range is 1 to 5, return 15.
Write a function the prints the squares between a given range inclusive
Write a function that sums up the individual digits in a given integer. Given, 12345, return 15
Write a function that verifies if a given year is a leap year. For a given input to be a leap year, it must be divisible by 4 but(and) not divisible by 100, or the input is divisible by 400.

Summary

A function is a block of code that performs a specific task
A function can take at least zero arguments
function definition

  def function_name(some_args):
      # some code

we can call the function by doing func_name(some_args)
A function allows reuse of code
A function can be used in any part of our code
parameters are passed into the function when creating the function
argument is what we pass to the function when we are calling it
return exits a function and returns a value from the function
use the *arg - tuple argument to collect more arguments
A function may be called as many times as possible
A recursive function calls itself
A lambda function is a nameless function, usually required on the fly

Python3 Programming - Exercise 12 c - Recursive and lambda functions