Python3 Programming - Exercise 12 c - Recursive and lambda functions
Tags: python, tutorial, beginners, programming
Published: 2021-02-03 17:41:09

## 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

```Python
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.

```Python
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

```Python
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.

```Python
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

```Python
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.

```Python
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

```Python
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.

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

```

Normally we would have written,

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


print(min_val(2, 4))  # 2
```

This is the same as :

```Python
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.

```Python
inc = (lambda n: n + 1)

print(inc(2))  # 3
```

Can you tell the difference between these two snippets  below?

```python
# 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

  ```Python
  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

#

[factorial]: https://en.wikipedia.org/wiki/Factorial
[Euclid GCD algorithm]: https://en.wikipedia.org/wiki/Euclidean_algorithm