# Python Program for Friends-Travel Problem

In this article, we’ll look at The Friends-Travel Problem, which is highly interesting.

Friends-Travel Problem:

Assume n friends want to go to a party; they can travel alone or with another friend as a couple. We presume that n motorbikes are offered for n buddies.

We need to figure out how many different ways the n friends can get to the party, either individually or in pairs of two as a couple.

One can either manually implement the naive technique using loops and if-else statements or use the quicker Recursion approach.

Before going into the problem just have a glance over the recursion.

To solve a larger problem, it is necessary to divide it into smaller difficulties.

Let us consider the lower values of n like ( 1, 2, and 3).

There are only one and two viable options for n = 1 and n = 2, respectively. And for n = 3, there are four alternative outcomes. How?

For each value of n, a friend has two options: either travel alone or search for n-1 friends.

Alternatively, the friend might choose a friend from the n-1 friends to travel with, and we will then look for n-2 friends.

Examples:

Example1:

Input:

Given number of friends = 3

Output:

Different ways the 3 friends can get to the party =  4

Example2:

Input:

Given number of friends = 5

Output:

Different ways the 5 friends can get to the party = 26

## Program for Friends-Travel Problem in Python

### Method #1: Using Recursion (Static Input)

Approach:

• Give the number(no of friends) as static input and store it in a variable.
• Create a recursive function say numberof_ways() which accepts the given number as an argument and returns the total number of ways friends can get to the party.
• Inside the function, check if the given number is less than 3 using the if conditional statement.
• If it is true, then return the given number.
• Return the value of {numberof_ways(no_frnds-1)) + ((no_frnds-1) * numberof_ways(no_frnds-2)} (Recursive Logic).
• Pass the given number as an argument to the numberof_ways() function and store it in a variable.
• Print the above result.
• The Exit of the Program.

Below is the implementation:

# Create a recursive function say numberof_ways() which accepts the given number
# as an argument and returns the total number of ways friends can get to the party.

def numberof_ways(no_frnds):
# Inside the function, check if the given number is less than 3 using the if
# conditional statement.
if(no_frnds < 3):
# If it is true, then return the given number.
return no_frnds
# Return the value of count_no_ways(no_frnds-1)) + ((no_frnds-1) *
# count_no_ways(no_frnds-2) (Recursive Logic).
return (numberof_ways(no_frnds-1)) + ((no_frnds-1) * numberof_ways(no_frnds-2))

# Give the number(no of friends) as static input and store it in a variable.
no_frnds = 3
# Pass the given number as an argument to the numberof_ways() function and
# store it in a variable.
rslt = numberof_ways(no_frnds)
# Print the above result.
print("Different ways the", no_frnds, "friends can get to the party = ", rslt)


Output:

Different ways the 3 friends can get to the party =  4

### Method #2: Using Recursion (User Input)

Approach:

• Give the number(no of friends) as user input using the int(input()) function and store it in a variable.
• Create a recursive function say numberof_ways() which accepts the given number as an argument and returns the total number of ways friends can get to the party.
• Inside the function, check if the given number is less than 3 using the if conditional statement.
• If it is true, then return the given number.
• Return the value of {numberof_ways(no_frnds-1)) + ((no_frnds-1) * numberof_ways(no_frnds-2)} (Recursive Logic).
• Pass the given number as an argument to the numberof_ways() function and store it in a variable.
• Print the above result.
• The Exit of the Program.

Below is the implementation:

# Create a recursive function say numberof_ways() which accepts the given number
# as an argument and returns the total number of ways friends can get to the party.

def numberof_ways(no_frnds):
# Inside the function, check if the given number is less than 3 using the if
# conditional statement.
if(no_frnds < 3):
# If it is true, then return the given number.
return no_frnds
# Return the value of count_no_ways(no_frnds-1)) + ((no_frnds-1) *
# count_no_ways(no_frnds-2) (Recursive Logic).
return (numberof_ways(no_frnds-1)) + ((no_frnds-1) * numberof_ways(no_frnds-2))

# Give the number(no of friends) as user input using the int(input()) function and store it in a variable.
no_frnds = int(input("Enter some random number = "))
# Pass the given number as an argument to the numberof_ways() function and
# store it in a variable.
rslt = numberof_ways(no_frnds)
# Print the above result.
print("Different ways the", no_frnds, "friends can get to the party = ", rslt)


Output:

Enter some random number = 5
Different ways the 5 friends can get to the party = 26